[163] 최소신장트리와 프림 알고리즘, 크루스칼 알고리즘

1. 그래프(graph)

그래프는 정점(vertex)과 간선(edge)을 가지는 자료구조입니다.

정점과 간선을 수학에서는 꼭짓점과 변으로 부릅니다.

https://ko.wikipedia.org/wiki/그래프_(자료_구조)

그래프 (자료 구조) - 위키백과, 우리 모두의 백과사전

2. 신장 부분 그래프(spanning subgraph)

어떤 그래프의 모든 정점을 포함하는 부분 그래프를 그 그래프의 신장 부분 그래프(spanning subgraph)라고 합니다.

https://ko.wikipedia.org/wiki/신장_부분_그래프

신장 부분 그래프 - 위키백과, 우리 모두의 백과사전

3. 신장 트리(spanning tree)

신장 부분 그래프 중 특별히 트리 구조이면 신장 트리(spanning tree)라고 합니다.

어떤 그래프에는 여러 개의 신장 트리가 존재할 수 있습니다.

https://en.wikipedia.org/wiki/Spanning_tree

Spanning tree - Wikipedia

4. 최소 신장 트리(minimum spanning tree)

신장 트리 중에 모든 간선이 가진 가중치의 합이 최소인 신장 트리를 최소 신장 트리(minimum spanning tree, MST) 또는 최소 비용 신장 트리(minimum weight spanning tree)라고 합니다.

위와 같은 그래프가 있을 때,

모든 정점을 위와 같이 연결하면 최소 신장 트리가 됩니다.

https://en.wikipedia.org/wiki/Minimum_spanning_tree

Minimum spanning tree - Wikipedia

5. 프림 알고리즘

그래프의 한 정점을 임의로 선택하여 그 정점을 시작점으로 모든 정점에 대해 최단거리를 구하며 연결하면 최소 신장 트리가 됩니다.

위 방법이 어디서 많이 본 것 같은데, 바로 다익스트라 알고리즘과 유사합니다.

다만 차이점은, 다익스트라 알고리즘에서는 최단 경로를 찾기 위해 지금까지의 가중치를 합하지만, 프림 알고리즘은 연결된 간선의 가중치를 그냥 사용합니다.

프림 알고리즘을 통해 최소 간선들을 찾아 이으면 그 경로는 시작점을 루트로 하는 트리 형태가 되고, 이 트리는 최소 신장 트리가 됩니다.

 

위의 최소 신장 트리를 찾는 코드는 다음과 같습니다.

from heapq import heappush, heappop

# 그래프 정보(인접 행렬)
graph = [
    [0, 6, 3, -1, 9, -1, -1, -1, -1, -1], 
    [6, 0, 4, 2, -1, -1, 9, -1, -1, -1], 
    [3, 4, 0, 2, 9, 9, -1, -1, -1, -1], 
    [-1, 2, 2, 0, -1, 8, 9, -1, -1, -1], 
    [9, -1, 9, -1, 0, 8, -1, -1, -1, 18], 
    [-1, -1, 9, 8, 8, 0, 7, -1, 9, 10], 
    [-1, 9, -1, 9, -1, 7, 0, 4, 5, -1], 
    [-1, -1, -1, -1, -1, -1, 4, 0, 1, 4], 
    [-1, -1, -1, -1, -1, 9, 5, 1, 0, 3], 
    [-1, -1, -1, -1, 18, 10, -1, 4, 3, 0]
]

# MST에 포함된 정점을 관리
in_mst = [0]*10

# MST 정보
total_cost = 0 # 비용
mst_edges = [] # 간선 정보

# 우선순위 큐에 시작 노드와 연결된 간선 정보를 담음
heap = []
for i in range(1, 10):
    if graph[0][i] != -1:
        heappush(heap, (graph[0][i], 0, i)) # (가중치, 이전 정점, 현재 정점)

# MST에 시작 노드 추가
in_mst[0] = 1

while heap:
    w, prev, cur = heappop(heap)

    # 이미 MST에 포함된 정점은 무시
    if in_mst[cur]:
        continue

    # MST 정보 추가
    in_mst[cur] = 1
    total_cost += w
    mst_edges.append((prev+1, cur+1, w))

    # 우선순위 큐에 다음 간선 정보 추가
    for nxt in range(10):
        if cur != nxt and graph[cur][nxt] != -1:
            heappush(heap, (graph[cur][nxt], cur, nxt))

print(total_cost)
# 38

print(*mst_edges, sep="\n")
# (1, 3, 3)
# (3, 4, 2)
# (4, 2, 2)
# (4, 6, 8)
# (6, 7, 7)
# (7, 8, 4)
# (8, 9, 1)
# (9, 10, 3)
# (6, 5, 8)

 

https://ko.wikipedia.org/wiki/프림_알고리즘

프림 알고리즘 - 위키백과, 우리 모두의 백과사전

6. 크루스칼 알고리즘

그래프의 모든 간선을 지우고, 간선을 가중치 오름차순으로 순회하며 간선을 다시 그립니다.

이미 연결되어 있는 정점 간의 간선은 무시합니다.(사이클이 생기지 않게 합니다.)

모든 정점이 연결되었을 때 최소 신장 트리가 됩니다.

이 알고리즘의 어떻게 특정 두 정점의 연결 여부를 확인하냐는 것 입니다.

이 또한 익숙한데, 바로 유니온파인드 알고리즘을 사용하면 두 정점이 연결되어있는지 확인할 수 있습니다.

위의 최소 신장 트리를 찾는 코드는 다음과 같습니다.

# 간선 정보(정점, 정점, 가중치)
edges = [
    [1, 2, 6],
    [1, 3, 3],
    [1, 5, 9],
    [2, 3, 4],
    [2, 4, 2],
    [2, 7, 9],
    [3, 4, 2],
    [3, 5, 9],
    [3, 6, 9],
    [4, 6, 8],
    [4, 7, 9],
    [5, 6, 8],
    [5, 10, 18],
    [6, 7, 7],
    [6, 9, 9],
    [6, 10, 10],
    [7, 8, 4],
    [7, 9, 5],
    [8, 9, 1],
    [8, 10, 4],
    [9, 10, 3]
]

# 유니온파인드 코드
parent = [i for i in range(10)]
rank = [0]*10
def find(u):
    if u != parent[u]:
        parent[u] = find(parent[u])
    return parent[u]
def union(u, v):
    u, v = find(u), find(v)
    if u != v:
        if rank[u] < rank[v]:
            parent[u] = v
            return
        if rank[u] == rank[v]:
            rank[u] += 1
        parent[v] = u

# MST 정보
total_cost = 0 # 비용
mst_edges = [] # 간선 정보

# 간선을 가중치 오름차순으로 정렬하여 하나씩 꺼냄
for u, v, w in sorted(edges, key=lambda x: x[2]):
    
    # 해당 간선 끝의 두 정점이 연결되어 있지 않다면
    if find(u-1) != find(v-1):

        # 두 정점을 연결
        union(u-1, v-1)

        # MST 정보 추가
        total_cost += w
        mst_edges.append((u, v, w))

print(total_cost)
# 38

print(*mst_edges, sep="\n")
# (8, 9, 1)
# (2, 4, 2)
# (3, 4, 2)
# (1, 3, 3)
# (9, 10, 3)
# (7, 8, 4)
# (6, 7, 7)
# (4, 6, 8)
# (5, 6, 8)

 

https://ko.wikipedia.org/wiki/크러스컬_알고리즘

크러스컬 알고리즘 - 위키백과, 우리 모두의 백과사전