[알고리즘] 신장트리 / 크루스칼 알고리즘 : 최소 신장 트리 알고리즘

신장트리 (Spanning Tree)

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

이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립조건이기도 하다.

 

 

예를 들어 다음과 같은 그래프가 있다고 하자.

위의 그래프에서 가능한 신장 트리는 다음과 같다. (여러개 존재 가능)

다음은 신장 트리가 될 수 없다. 사이클이 존재하기 때문이다.

다음도 신장 트리가 될 수 없다. 노드 2를 포함하고 있지 않기 때문이다.

---

최소 신장 트리 알고리즘

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

최소 신장 트리의 간선의 개수는 '노드의 개수 - 1'이다.

대표적인 최소 신장 트리 알고리즘으로는 크루스칼 알고리즘이 있다.

 

예

다음과 같이 3개이 도시가 있고 각 도시 간 도로를 건설하는 비용은 23, 13, 25이다.

 

① 신장 트리

비용 : 23 + 13 = 36 

② 신장 트리

비용 : 23 + 25 = 48

 

③ 신장 트리

비용 : 13 + 25 = 38

①이 최소 비용이기 때문에, ①을 최소 신장 트리라고 한다.

---

 

 

크루스칼 알고리즘 (Kruskal Algorithm)

크루스칼 알고리즘을 사용하면 최소 비용으로 모든 노드를 연결할 수 있는데, 크루스칼 알고리즘은 그리디 알고리즘으로 분류된다. 

 

원리

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

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

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

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

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

 

예제

step 0

간선 데이터를 오름차순으로 정렬한다.

간선	(1, 3)	(3, 5)	(4, 5)	(2, 4)	(1, 2)	(1, 4)	(1, 5)
비용	7	13	22	25	29	34	53

parent 테이블은 자기 자신으로 초기화한다.

노드 번호	1	2	3	4	5
부모(루트 노드)	1	2	3	4	5

 

step 1

가장 짧은 간선인 (1, 3)을 선택한다.

1의 루트 노드를 찾는다. → 1

3의 루트 노드를 찾는다. → 3

루트 노드가 다르다 → 사이클이 발생하지 않았다 → 집합에 포함시킨다 = 합집합(union)을 수행한다

더 큰 번호에 해당하는 루트 노드 3을 자식 노드로 설정하고, 더 작은 번호에 해당하는 루트 노드 1을 부모 노드로 설정한다.

 

parent 테이블

노드 번호	1	2	3	4	5
부모(루트 노드)	1	2	1	4	5

 

step 2

그 다음으로 짧은 간선인 (3, 5)를 선택한다.

3의 루트 노드를 찾는다. → 1

5의 루트 노드를 찾는다. → 5

루트 노드가 다르다 → 사이클이 발생하지 않았다 → 집합에 포함시킨다 = 합집합(union)을 수행한다

더 큰 번호에 해당하는 루트 노드 5를 자식 노드로 설정하고, 더 작은 번호에 해당하는 루트 노드 1을 부모 노드로 설정한다.

 

parent 테이블

노드 번호	1	2	3	4	5
부모(루트 노드)	1	2	1	4	1

 

step 3

그 다음으로 짧은 간선인 (4, 5)를 선택한다.

4의 루트 노드를 찾는다. → 4

5의 루트 노드를 찾는다. → 1

루트 노드가 다르다 → 사이클이 발생하지 않았다 → 집합에 포함시킨다 = 합집합(union)을 수행한다

더 큰 번호에 해당하는 루트 노드 4를 자식 노드로 설정하고, 더 작은 번호에 해당하는루트  노드 1을 부모 노드로 설정한다.

 

parent 테이블

노드 번호	1	2	3	4	5
부모(루트 노드)	1	2	1	1	1

 

step 4

그 다음으로 짧은 간선인 (2, 4)를 선택한다.

2의 루트 노드를 찾는다. → 2

4의 루트 노드를 찾는다. → 1

루트 노드가 다르다 → 사이클이 발생하지 않았다 → 집합에 포함시킨다 = 합집합(union)을 수행한다

더 큰 번호에 해당하는 루트 노드 2를 자식 노드로 설정하고, 더 작은 번호에 해당하는루트  노드 1을 부모 노드로 설정한다.

 

parent 테이블

노드 번호	1	2	3	4	5
부모(루트 노드)	1	1	1	1	1

 

step 5

그 다음으로 짧은 간선인 (1, 2)를 선택한다.

1의 루트 노드를 찾는다. → 1

2의 루트 노드를 찾는다. → 1

루트 노드가 같다 → 사이클이 발생하였다 → 집합에 포함시키지 않는다

 

step 6

그 다음으로 짧은 간선인 (1, 4)를 선택한다.

1의 루트 노드를 찾는다. → 1

4의 루트 노드를 찾는다. → 1

루트 노드가 같다 → 사이클이 발생하였다 → 집합에 포함시키지 않는다

 

step 7

그 다음으로 짧은 간선인 (1, 5)를 선택한다.

1의 루트 노드를 찾는다. → 1

5의 루트 노드를 찾는다. → 1

루트 노드가 같다 → 사이클이 발생하였다 → 집합에 포함시키지 않는다

 

크루스칼 알고리즘 종료 결과

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

최소 신장 트리에 포함되어 있는 간선의 비용만 모두 더하면, 그 값이 최종 비용에 해당하기 때문에 최소 비용은 7 + 13 + 22 + 25 = 67이다. 

 

---

입력 예시

5 7 
1 2 29
1 3 7
1 4 34
1 5 53
2 4 25
3 5 13
4 5 22

출력 예시

67

소스 코드

# 특정 원소가 속한 집합 찾기 = 루트 노드 찾기
# 루트 노드가 같으면 같은 집합에 속한 것
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


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)