[알고리즘] Minimum Spanning Tree - Kruskal & Prim Algorithm

최소 신장 트리 (Minimum Spanning Tree, MST)

---

최소 신장 트리는 주어진 그래프의 모든 정점을 연결하는 부분 그래프 중, 그 가중치의 합이 최소인 트리를 말한다.

* 부분 그래프(Subgraph) : 주어진 그래프에서 일부 정점과 간선만을 선택하여 구성한 그래프

 

더 쉽게 말하자면 가장 적은 비용으로 모든 노드를 연결한 그래프를 말하며, 이때 사이클이 발생하면 안 된다.

 

사이클이 발생한 경우 : 불가

 

* 정점 = 노드

* 간선 = 비용 = 가중치 (그래프에서 선에 해당하는 부분)

 

 

동일한 그래프에서 최소 신장 트리는 여러 개가 나올 수 있다. 가중치의 합이 최소이기만 하면 되기 때문이다.

 

---

최소 신장 트리를 구하기 위한 알고리즘은 2가지가 존재하며, 각각 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이다.

 

두 알고리즘의 핵심 아이디어는 "가중치가 작은 간선을 부분 그래프에 먼저 포함"시키는 것으로 비슷하며,

구현을 하는 방식과 사용하는 자료구조만 다를 뿐이다.

 

구현은 크루스칼 알고리즘이 프림 알고리즘보다 더욱 간단하다.

 

 

이제 두 알고리즘 각각과 그의 구현 코드(Python)에 대하여 차례대로 알아보자.

예시로는 아래의 그래프를 사용할 것이다.

 

 

구현 코드는 백준 1197번 문제에 대한 Python 코드이다.

1197번: 최소 스패닝 트리

 

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

---

구현 by. Union-Find

[알고리즘] Disjoint Set & Union-Find

 

큰 흐름은 다음과 같다.

1. 모든 간선의 정보를 저장
2. 가중치 기준 오름차순 정렬

3. 정렬된 순서대로 간선을 그래프에 포함
	1. 포함하기 전, 사이클이 발생하는지를 확인 (by. Union-Find)
	2. 사이클이 발생할 경우 해당 간선을 그래프에 포함하지 않음

 

예시

1. 모든 간선의 정보를 저장

 

노드 (1)	노드 (2)	가중치
1	2	3
1	3	3
1	4	6
1	5	4
2	3	1
3	5	4
4	5	1
4	6	2
5	6	3

 

2. 가중치 기준 오름차순 정렬

 

노드 (1)	노드 (2)	가중치
2	3	1
4	5	1
4	6	2
1	2	3
1	3	3
5	6	3
1	5	4
3	5	4
1	4	6

 

3. 정렬된 순서대로 간선을 그래프에 포함시킴

 

이때 사이클이 발생하면 안 되는데, 이는 Union-Find 알고리즘을 통해서 확인한다.

 

우선 Union-Find 알고리즘을 위해서는 각 노드가 어느 노드를 부모(root)로 가지고 있는지를 확인할 수 있는 리스트가 필요하다.

초기화 시 부모 노드의 번호는 자기 자신과 같다.

 

노드 번호	1	2	3	4	5	6
부모 노드의 번호	1	2	3	4	5	6

 

2번에서 가중치 기준 오름차순 정렬을 한 후의 순서대로 간선들을 그래프에 포함시켜 보자.

 

(1) 노드 2 - 노드 3

 

즉, 노드 2가 노드 3의 부모가 된 것이다.

가중치 합 : 1

 

노드 번호	1	2	3	4	5	6
부모 노드의 번호	1	2	2	4	5	6

 

(2) 노드 4 - 노드 5

 

사이클이 발생하지 않으므로 추가 가능하다.

가중치 합 : 1+1 = 2

 

노드 번호	1	2	3	4	5	6
부모 노드의 번호	1	2	2	4	4	6

 

(3) 노드 4 - 노드 6

 

사이클이 발생하지 않으므로 추가 가능하다.

가중치 합 : 2+2 = 4

 

노드 번호	1	2	3	4	5	6
부모 노드의 번호	1	2	2	4	4	4

 

(4) 노드 1 - 노드 2

 

사이클이 발생하지 않으므로 추가 가능하다.

가중치 합 : 4+3 = 7

 

노드 번호	1	2	3	4	5	6
부모 노드의 번호	2	2	2	4	4	4

 

이때 find() 함수를 통해서 "노드 1의 부모는 노드 3 → 노드 3의 부모는 노드 2 → 노드 2의 부모는 노드 2 → 따라서 root는 노드 2"라는 것을 알 수 있다.

 

(5) 노드 1 - 노드 3

 

노드 1, 2, 3 사이에 사이클이 발생하기 때문에 이 간선은 그래프에 추가할 수 없다.

이는 find 함수를 통하여 3개의 노드 전부 부모가 노드 2인 것을 확인할 수 있기 때문에 해당 간선을 걸러낼 수 있게 된다.

 

(6) 노드 5 - 노드 6

 

여기서도 사이클이 발생하기 때문에 이 간선은 그래프에 추가할 수 없다. (부모 노드가 전부 4이기 때문)

 

(7) 노드 1 - 노드 5

 

사이클이 발생하지 않으므로 추가 가능하다.

가중치 합 : 7+4 = 11

 

노드 번호	1	2	3	4	5	6
부모 노드의 번호	2	2	2	2	2	2

 

이렇게 모든 노드가 연결이 되었고, 가중치 합의 최솟값은 11이 된다.

 

여기서는 아직 직접 확인해보지 않은 간선들이 남아있으나, find 함수를 통해 모든 간선이 사이클을 유발함을 알아내기 때문에 그래프에 추가되지 않는다.

 

구현 (Python)

import sys

input = sys.stdin.readline

V, E = map(int, input().split())  # 노드의 개수, 간선의 개수
parent = [i for i in range(V + 1)]

kruskal = []
for i in range(E):
    A, B, C = map(int, input().split())  # 노드 a, 노드 b, 가중치 w
    kruskal.append((A, B, C))
kruskal.sort(key=lambda x: x[2])  # 가중치 기준 오름차순 정렬


def union(a, b):
    root_a, root_b = find(a), find(b)
    parent[max(root_a, root_b)] = min(root_a, root_b)


def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x])  # 최적화를 위한 Path Compression
    return parent[x]


min_weight = 0
for a, b, w, in kruskal:
    if find(a) != find(b):
        min_weight += w
        union(a, b)

print(min_weight)

 

프림 알고리즘 (Prim Algorithm)

---

구현 by. 우선순위 큐

 

큰 흐름은 다음과 같다.

1. 임의의 정점 하나를 선택하여 그래프에 포함
2. 해당 정점과 연결된 모든 간선을 우선순위 큐에 push

3. 우선순위 큐에서 가중치가 가장 작은 간선을 선택

4. 해당 간선이 그래프에 포함되어 있는 두 정점을 연결한다면 pass
5-1. 해당 간선이 그래프에 포함된 정점 하나(u)와 포함되지 않은 정점 하나(v)를 연결한다면 해당 간선과 정점(v)을 그래프에 추가
5-2. 정점 v와 그래프에 포함되지 않은 정점들을 연결하는 모든 간선을 우선순위 큐에 push

6. 그래프에 (전체 노드의 개수 - 1)개의 간선이 추가될 때까지 3, 4, 5번의 과정을 반복

 

예시

1. 임의의 정점 하나를 선택하여 그래프에 포함

임의로 노드 1을 선택하겠다.

 

 

2. 해당 정점과 연결된 모든 간선을 우선순위 큐에 push

* 우선순위 큐에 push 되어 있는 간선들은 붉은색으로 표시

 

아래 표는 우선순위 큐를 나타낸 것이다.

우선순위 큐는 이진 트리 형태를 가지고 있지만, 지금은 우선순위 큐의 동작 원리가 중요한 것이 아니기 때문에 표 형태로 나타낸 후 이곳에서 가장 작은 가중치를 가지는 간선을 pop 하겠다.

 

노드 (1)	노드 (2)	가중치
1	2	3
1	3	3
1	4	6
1	5	4

 

3. 우선순위 큐에서 가중치가 가장 작은 간선을 선택

현재 가장 작은 가중치를 가지는 간선은 노드 1과 노드 2를 연결하는 간선이다.

이를 우선순위 큐에서 pop 한다.

 

노드 (1)	노드 (2)	가중치
1	3	3
1	4	6
1	5	4

 

4. 해당 간선이 그래프에 포함되어 있는 두 정점을 연결하는지 확인, 그래프에 추가

이는 아직 그래프에 포함되지 않은 노드 2를 연결하기 때문에 노드 2와 해당 간선을 그래프에 추가하여야 한다.

* 그래프에 포함된 노드와 간선은 푸른색으로 표시

 

 

가중치 합 : 3

 

5. 현재 그래프에 포함되어 있는 노드들에 대하여, 그래프에 포함되지 않은 정점들을 연결하는 모든 간선을 우선순위 큐에 push

노드 2가 그래프에 새로 포함되었으므로 노드 2와 연결된 간선들을 확인하여 우선순위 큐에 push 해야 한다.

그러한 간선들은 노드 2와 노드 3을 연결하는 간선만 있으므로 이를 우선순위 큐에 push 한다.

 

 

노드 (1)	노드 (2)	가중치
1	3	3
1	4	6
1	5	4
2	3	1

 

이 과정을 그래프에 (전체 노드의 개수 - 1)개의 간선이 추가될 때까지 계속 반복해야 한다.

아래에 그 과정을 쭉 나타내보도록 하겠다.

 

선택 / 확인 / push

(1) 우선순위 큐에서 선택된 간선 : 노드 2 - 노드 3, 가중치 1

(2) 그래프에 아직 포함되지 않은 노드 3을 연결함 → 해당 간선과 노드 3을 그래프에 포함

(3) 노드 3과 연결된 간선을 우선순위 큐에 push

 

 

노드 (1)	노드 (2)	가중치
1	3	3
1	4	6
1	5	4
3	5	4

 

가중치 합 : 3+1 = 4

 

선택 / 확인 / push? → no.

(1) 우선순위 큐에서 선택된 간선 : 노드 1 - 노드 3, 가중치 3

(2) 노드 1과 노드 3은 전부 그래프에 포함되어 있음 → 해당 간선은 그래프에 포함하지 않음

 

노드 (1)	노드 (2)	가중치
1	4	6
1	5	4
3	5	4

 

선택 / 확인 / push

(1) 우선순위 큐에서 선택된 간선 : 노드 1 - 노드 5, 가중치 4

(2) 그래프에 아직 포함되지 않은 노드 5를 연결함 → 해당 간선과 노드 5를 그래프에 포함

(3) 노드 5와 연결된 간선을 우선순위 큐에 push

 

 

노드 (1)	노드 (2)	가중치
1	4	6
3	5	4
5	4	1
5	6	3

 

가중치 합 : 4+4 = 8

 

선택 / 확인 / push

(1) 우선순위 큐에서 선택된 간선 : 노드 5 - 노드 4, 가중치 1

(2) 그래프에 아직 포함되지 않은 노드 4를 연결함 → 해당 간선과 노드 4를 그래프에 포함

(3) 노드 4와 연결된 간선을 우선순위 큐에 push

 

 

노드 (1)	노드 (2)	가중치
1	4	6
3	5	4
5	6	3
4	6	2

 

가중치 합 : 8+1 = 9

 

선택 / 확인 / push

(1) 우선순위 큐에서 선택된 간선 : 노드 4 - 노드 6, 가중치 2

(2) 그래프에 아직 포함되지 않은 노드 6을 연결함 → 해당 간선과 노드 6을 그래프에 포함

(3) 노드 6와 연결된 간선을 우선순위 큐에 push (더 이상 없음)

 

 

노드 (1)	노드 (2)	가중치
1	4	6
3	5	4
5	6	3

 

가중치 합 : 9+2 = 11

 

종료

총 5개의 간선이 그래프에 들어갔으므로 알고리즘은 종료되고 푸른색으로 표시된 부분이 최소 신장 트리이다.

해당 부분만 뽑아서 보면 아래와 같으며, 가중치 합의 최솟값은 11이 된다.

 

 

이 결과는 위에서 먼저 알아보았던 크루스칼 알고리즘에서의 결과와 똑같다.

어느 간선이 먼저 뽑혔느냐에 따라 다음과 같은 모양들도 나올 수 있다. 가중치의 합은 11로 동일하다.

 

 

 

구현 (Python)

import sys
import heapq
from collections import defaultdict

input = sys.stdin.readline

V, E = map(int, input().split())  # 노드의 개수, 간선의 개수
visited = [False for _ in range(V + 1)]  # 노드 방문 정보

# 무방향 그래프 (가중치, 자기 자신, 연결된 노드)
graph = defaultdict(list)
for _ in range(E):
    A, B, C = map(int, input().split())  # 노드 a, 노드 b, 가중치 w
    graph[A].append((C, A, B))
    graph[B].append((C, B, A))


def prim(graph, start_node):
    visited[start_node] = True

    mst = []
    min_weight = 0

    # 우선순위 큐
    candidate_edge = graph[start_node]
    heapq.heapify(candidate_edge)

    while candidate_edge:
        w, a, b = heapq.heappop(candidate_edge)

        if not visited[b]:
            visited[b] = True
            mst.append((a, b))
            min_weight += w

            for edge in graph[b]:
                if not visited[edge[2]]:
                    heapq.heappush(candidate_edge, edge)

    return min_weight


print(prim(graph, 1))

 

문제 추천

---

1647번: 도시 분할 계획

21924번: 도시 건설

1774번: 우주신과의 교감

14621번: 나만 안되는 연애

1368번: 물대기