최소신장트리 - 바킹독

정의와 성질

신장트리란 주어진 방향성이 없는 그래프틔 부분 그래프들 중에서 모든 정점을 포함하는 트리를 의미한다.

최소신장트리란 신장트리 중에서 간선의 합이 최소인 트리를 말한다.

크루스칼 알고리즘

1. 간선을 크기의 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택
2. 현재 선택한 간선이 정점 u, v를 연결하는 간선이라고 할 때 만약 u와 v가 같은 그룹이라면 아무것도 하지 않고 넘어감 u와 v가 다른 그룹이라면 같은 그룹으로 만들고 현재 선택한 간선을 최소 신장트리에 추가
3. 최소 신장트리에 v-1개의 간선을 추가시켰다면 과정을 종료, 그렇지 않다면 그 다음으로 비용이 작은 간선을 선택한 후 2번 과정을 반복

크루스칼 알고리즘은 가장 비용이 작은 간선을 택하는 그리디 알고리즘이다.

크루스칼 알고리즘의 실제구현 코드는 union find를 알지 못한하면 완성할 수가 없다.

문제는 특정 두 정점이 같은 그룹인지 다른 그룹인지 어떻게 판단할 수 있느냐 하는건데 현재 공부한 내용을 바탕으로 하면 flood fill을 이용해 해결할 수 있다.

최소신장 트리에 편입시킨 간선을 별도로 관리하고 있다고 할 때 정점 A와 B가 같은 그룹인지 확인하고 싶다면 최소신장트리에 편입시킨 간선들만 가지고 A에서 B로 갈 수 있는지 즉 A에서 flood fill을 돌렸을 때 B를 방문하는지 확인하면 된다.

그러나 시간복잡도는 간선을 정렬하는데 O(ElogE) 가 필요하고 그래프를 방문 순회하는데 O(VE)가 필요하다. 최종적으로 O(ElogE + VE)라는 비효율적인 시간복잡도가 발생한다.

union find를 활용하면 같은 그룹인지 아닌지 사실상 상수시간에 확인할 수있다(?!?! 아커만 역함수??)

프림알고리즘

프림알고리즘 또한 가장 비용이 낮은 간선을 택하는 그리디 알고리즘이다.

프림알고리즘의 방법은 이해하기 쉬우나 구현자체의 난이도가 높다.

1. 임의의 정점을 선택해 최소 신장트리에 추가
2. 최소 신장트리에 포함된 정점과 최소 신장트리에 포함되지 않은 정점을 연결하는 간선 중 비용이 가장 작은 것을 최소 신장트리에 추가
3. 최소 신장트리에 v-1개의 간선이 추가될 때까지 2번 과정을 반복

위 방식대로 구현하려고 한다면 v-1번에 걸쳐 현재 최소 간선 트리에 포함된 정점과 포함되지 않은 정점을 연결하는 모든 간선을 조사하고 이들중에서 최소비용인 간선을 택하는 방식으로 구현을 할 수 있다. 하지만 이렇게 구현을하면 O(VE) 시간복잡도를 가지기 때문에 비효율적이다.

프림 알고리즘을 더 효율적으로 구현하기 위해서는 우선순위 큐가 필요하다.

1. 임의의 정점을 선택해 최소 신장트리에 추가, 해당 정점과 연결된 모든 간선을 우선순위 큐에 추가해준다.
2. 우선선위 큐에서 비용이 가장 작은 간선을 선택
3. 만약 해당 간선이 최소 신장트리에 포함된 두 정점을 연결한다면 아무것도 하지 않고 넘어감, 해당 간선이 최소 신장트리에 포함된 정점 u와 포함되지 않은 정점 v를 연결한다면 해당간선과 정점 v를 최소 신장 트리에 추가 후 정점 v와 최소 신장트리에 포함되지 않는 정점을 연결하는 모든 간선을 우선순위 큐에 추가
4. 최소 신장트리 v-1개의 간선이 추가될 때까지 2, 3번 과정을 반복

연습문제

boj-1197

import heapq
import sys
input = sys.stdin.readline
V, E = map(int, input().split())

edges = [[ ] for _ in range(V+1)]
spanning_tree = [0] * (V+1)
priority_queue = []
cnt = 0
answer = 0

for _ in range(E):
    edge1, edge2, cost = map(int, input().split())
    edges[edge1].append((cost, edge2))
    edges[edge2].append((cost, edge1))
    
spanning_tree[1] = 1
for node in edges[1]:
    heapq.heappush(priority_queue, (node[0], 1, node[1]))

while cnt < V-1:
    cost, start_edge, end_edge = heapq.heappop(priority_queue)
    
    if spanning_tree[end_edge]: continue
    
    spanning_tree[end_edge] = 1
    cnt += 1
    answer += cost
    for next_node in edges[end_edge]:
        if not spanning_tree[next_node[1]]:
            heapq.heappush(priority_queue,(next_node[0], end_edge, next_node[1]))

print(answer)

boj-1368

우물을 파는 방법이 주어진다. 이 우물파는 방법을 하나의 다른 정점으로 생각해서 정점을 만들고 그대로 프림 알고리즘을 통해서 최소값을 구해주면 된다.

import heapq
import sys
input = sys.stdin.readline

V = int(input().rstrip())
edges = [[ ] for _ in range(V+2)]
for i in range(1, V+1):
    cost = int(input().rstrip())
    edges[i].append((cost, V+1))
    edges[V+1].append((cost, i))
    
for i in range(1, V+1):
    for j, value in enumerate(list(map(int, input().rstrip().split())),1):
        if i >= j:
            continue
        edges[i].append((value, j))
        edges[j].append((value, i))

spanning_tree = [0] * (V+2)
spanning_tree[1] = 1

cnt = 0
answer = 0
priority_queue = []
for node in edges[1]:
    heapq.heappush(priority_queue, node)

while cnt < V:
    cost, end_edge = heapq.heappop(priority_queue)
    if not spanning_tree[end_edge]:
        answer += cost
        spanning_tree[end_edge] = 1
        cnt +=1
        for next_node in edges[end_edge]:
            if not spanning_tree[next_node[1]]:
                heapq.heappush(priority_queue, next_node)

print(answer)