[ 그래프] - 신장트리와 크루스칼 알고리즘

 

신장트리

하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

위와 같은 하나의 그래프는 왼쪽 아래의 그래프와 같이 여러개의 신장 트리를 가질수 있다.

또한 오른쪽 아래 2개의 그래프와 같이 노드1을 포함하지 않거나 사이클이 존재할 경우 신장 트리가 아니다.

 

크루스칼 알고리즘

모든 도시를 최소한의 비용으로 연결 하는 경우에 대한 예시를 들어보자.

왼쪽과 같은 그래프는 3개의 도시가 있고 각각 도시 간 도로를 건설하는 비용은 23,13,25이다.

여기서 노드 1,2,3을 모두 연결하지 위한 가장 최소한의 비용을 가지는 신장 트리는 36이다.

1) 23 + 13 = 36

2) 23 + 25 = 48

3) 25 + 13 = 38

이처럼 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 '최소 신장 트리 알고리즘' 이라고 한다.

그 대표적인 알고리즘이 바로 크루스칼 알고리즘이다.

 

 

크로스칼 알고리즘은 그리드 알고리즘으로 분류가 된다.

먼저 모든 간선에 대하여 정렬을 수행한 뒤 가장 거리가 짧은 간선부터 집합에 포함 시키면 된다.

이때 사이클이 발생시킬수 있는 간선일 경우, 집합에 포함시키지 않는다.

 

구체적인 크로스칼 알고리즘은 아래와 같다.

1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.

2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.

         1) 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다

         2) 사이클이 발생하는 경우 최소 신장 트리에 포함 시키지 않는다.

3. 모든 간선에 대하여 2번 과정을 반복한다. 

 

 

 

아래 그래프의 최소 신장 트리를 구해보자.

최소 신장 트리는 바로 오른쪽 그래프와 같이 하늘색 간선을 포함 시키면 만들 수 있다.

 

 

STEP 0 그래프의 간선 정보만 따로 정렬을 수행한다.

실제로는 전체 간선 데이터를 리스트에 담은 뒤 이를 정렬하지만 , 가독성을 위해 노드 데이터 순서에 따라 테이블 내에서 데이터를 나열.

 

 

STEP 1 가장 짧은 간선을 선택한다.

따라서 (3,4)가 선택되고 이것을 집합에 포함하면된다.

즉, 노드 3과 노드4에 대해 Union함수를 수행하여 같은 집합에 속하도록 한다.

 

 

STEP 2  그 다음으로 비용이 가장 작은 간선인 (4,7)을 선택한다.

현재 노드 4와 노드7은 같은 집합에 속해 있지 않기 때문에 union함수를 호출한다.

 

 

 

 

 

 

STEP 3 그 다음 비용이 작은 간선인 (4,6)을 선택한다.

현재 노드 4와 노드6은 같은 집합에 속해 있지 않기 때문에 union함수를 호출한다.

 

 

 

STEP 4 그 다음 비용이 가장 적은 간선인 (6,7)을 선택한다.

노드 6과7의 루트노드는 이미 동일한 집합에 있으므로 신장 트리에 포함하지 말아야 한다.

( 처리가 되었지만 신장트리에 포함하지 않은 간선은 점선으로 표시)

 

--------------------------위와 같은 과정을 반복-----------------------------------

 

 

결과 적으로 위와 같은 최소 신장 트리를 찾을 수 있다.

또한 최소 신장 트리에 포함되어 있는 간선의 비용만 모두 더하면 그 값이 최종 비용이 된다.

 

 

크루스칼 알고리즘 소스코드

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화하기

# 모든 간선을 담을 리스트와, 최종 비용을 담을 변수
edges = []
result = 0

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

# 모든 간선에 대한 정보를 입력 받기
for _ in range(e):
    a, b, cost = map(int, input().split())
    # 비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정
    edges.append((cost, a, b))

# 간선을 비용순으로 정렬
edges.sort()

# 간선을 하나씩 확인하며
for edge in edges:
    cost, a, b = edge
    # 사이클이 발생하지 않는 경우에만 집합에 포함
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost

print(result)

 

 

 

시간 복잡도

간선의 개수가 E개 일때 O(ElogE)의 시간 복잡도를 가진다.

왜냐하면 가장 시간이 오래 걸리는 부분이 간선을 정렬하는 작업이기 때문이다.

크루스칼 내부에서 사용되는 서로서 집합 알고리즘의 시간 복잡도는 정렬 알고리즘의 시간 복잡도 보다 작으므로 무시한다.