신장트리와 크루스칼 알고리즘

신장트리

모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는 부분 그래프

 

 

그렇다면, 신장트리가 왜 필요할까? 어느 문제에서 쓰일 수 있을까?

 

예를들어 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 최소비용으로 서로 연결될 수 있게 도로를 설치하는 경우를 생각해보자.

 

N개의 도시를 다 연결하기 위해서 모든 노드가 포함되어야 하고

최소비용으로 연결하기 위해서 사이클이 존재하지 않고, 최소비용의 간선만 존재해야 한다.

 

 

 

그러면 주어진 데이터에서 신장트리를 어떻게 만들 수 있을까?

 

 

 

 

 

크루스칼 알고리즘

대표적인 최소 신장 트리를 구할 수 있는 알고리즘이다.

 

구현방법

1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
   1) 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
   2) 사이클이 발생하는 경우 최소 신장트리에 포함하지 않고 무시한다.
3. 모든 간선에 대하여 2번의 과정을 반복한다.

 

간선	(1, 2)	(1, 5)	(2, 3)	(2, 6)	(3, 4)	(4, 6)	(4, 7)	(5, 6)	(6, 7)
비용	29	75	35	34	7	23	13	53	25

 

먼저, 비용을 기준으로 오름차순 정렬을 수행한다.

(여기서는 정렬을 수행했다고 가정하고 가장 비용이 적은 간선부터 선택할 것이다.)

 

 

가장 비용이 적은 간선인 7을 선택한다.

사이클이 발생하지 않는다.

최소 신장트리에 포함한다.

 

간선	(1, 2)	(1, 5)	(2, 3)	(2, 6)	(3, 4)	(4, 6)	(4, 7)	(5, 6)	(6, 7)
비용	29	75	35	34	7	23	13	53	25
순서					1

 

 

 

그다음 비용이 적은 간선인 13을 선택한다.

사이클이 발생하지 않는다.

최소 신장트리에 포함한다.

 

간선	(1, 2)	(1, 5)	(2, 3)	(2, 6)	(3, 4)	(4, 6)	(4, 7)	(5, 6)	(6, 7)
비용	29	75	35	34	7	23	13	53	25
순서					1		2

 

 

 

그다음 비용이 적은 간선인 23을 선택한다.

사이클이 발생하지 않는다.

최소 신장트리에 포함한다.

간선	(1, 2)	(1, 5)	(2, 3)	(2, 6)	(3, 4)	(4, 6)	(4, 7)	(5, 6)	(6, 7)
비용	29	75	35	34	7	23	13	53	25
순서					1	3	2

 

 

 

그다음 비용이 적은 간선인 25을 선택한다.

사이클이 발생한다.

최소 신장트리에 포함하지 않는다.

간선	(1, 2)	(1, 5)	(2, 3)	(2, 6)	(3, 4)	(4, 6)	(4, 7)	(5, 6)	(6, 7)
비용	29	75	35	34	7	23	13	53	25
순서					1	3	2		4

 

 

 

그다음 비용이 적은 간선인 29을 선택한다.

사이클이 발생하지 않는다.

최소 신장트리에 포함한다.

간선	(1, 2)	(1, 5)	(2, 3)	(2, 6)	(3, 4)	(4, 6)	(4, 7)	(5, 6)	(6, 7)
비용	29	75	35	34	7	23	13	53	25
순서	5				1	3	2		4

 

 

 

위와같은 연산을 계속 수행하면 아래와 같이 된다.

간선	(1, 2)	(1, 5)	(2, 3)	(2, 6)	(3, 4)	(4, 6)	(4, 7)	(5, 6)	(6, 7)
비용	29	75	35	34	7	23	13	53	25
순서	5	9	7	6	1	3	2	8	4

 

 

결국 아래와 같은 신장트리가 나오게 된다.

 

 

 

 

 

 

 

코드로 구현

def find_parent(parent, x):
    if parent[x] != x:
        return find_parent(parent, x)
    return x


def union_parent(parent, a, b):
    a = find_parent(a)
    b = find_parent(b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b


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)

 

 

find_parent 함수와 union_parent 함수는 union_find 구현법과 동일하고

간선에 대한 정보를 넣는 방식이 달라졌다.

 

그리고 정렬된 간선의 정보들을 차례로 꺼내서 사이클 판별 후 비용들을 더해 최소비용을 구할 수 있다.

 

 

 

 

 

크루스칼 알고리즘의 시간복잡도

간선을 정렬하는 부분이 가장 많은 연산을 하는 부분이다.

표준 라이브러리를 이용해 정렬하면 log(E log E) 에 정렬할 수 있다. (E는 간선의 개수)