소개
최소 신장 트리 문제는 하나의 연결 요소를 가진 양방향 연결 그래프에서 각 간선들의 가중치가 주어졌을 때, 연결 요소를 두 개 이상으로 쪼개지 않으면서 간선들 중 일부를 제거하여 가중치의 총합이 최소가 되도록 하는 문제이다. 그래프에서 정의된 이 문제가 최소 신장 "트리"로 불리는 이유는 정점의 개수가
해결
크루스칼
크루스칼 알고리즘은 최소 신장 트리 문제를 탐욕법 매커니즘으로 해결한다. 우선 그래프의 간선을 전부 떼어놓고 가중치가 작은 순으로 정렬한다. 그리고 첫 간선부터 검사하며 그래프에
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
우선 그래프에서 간선을 전부 떼어낸다. 떼어낸 간선들은 가중치 순으로 정렬한다.
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
이제 이 그래프에서 가중치가 작은 간선부터 하나씩 추가한다. 제일 먼저 가중치가 2인 정점
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
그 다음 간선은 가중치가 3인 정점
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
그 다음 간선은 가중치가 5인 정점
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
그 다음 간선은 가중치가 6인 정점
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
바로 이 트리가 해당 그래프의 최소 신장 트리인 것이다. 크루스칼 알고리즘은 그래프의 간선의 개수가
구현
간선을 채택했을 때 사이클이 발생하는지의 여부는 분리 집합을 통해서 알아낸다. 간선을 하나씩 검사할 때마다 find
연산을 사용해 같은 연결 집합에 존재하는지를 알아낸 후, 같은 연결 집합에 속하지 않았다면 간선의 양 쪽의 연결 집합을 하나의 집합으로 합쳐주면서 진행한다.
# edge는 간선 리스트로, 다음과 같은 형태를 띤다.
# edge[m] = (a, b, cost)
def kruskal(n: int, edge: list[tuple[int, int, int]]) -> list[tuple[int, int, int]]:
result: list[tuple[int, int, int]] = []
root = [i for i in range(n)]
def find(i: int) -> int:
if root[i] != i:
root[i] = find(root[i])
return root[i]
for a, b, cost in sorted(edge, key=lambda e: e[2]):
root_a, root_b = find(a), find(b)
if root_a != root_b:
root[root_a] = root_b
result.append((a, b, cost))
if len(result) == N - 1:
return result
raise
프림
크루스칼 알고리즘이 간선 위주의 알고리즘이었다면, 프림 알고리즘은 정점 위주의 알고리즘이다. 프림 알고리즘은 정점 하나에서 시작하여, 연결 집합에 바로 연결된 간선 중 사이클이 생기지 않으면서 가중치가 최소인 간선을 선택해 연결 집합을 확장해나가는 방식으로 진행된다. 예시를 보자.
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
먼저 그래프의 아무 정점이나 하나 고르고 시작 정점으로 정한다. 시작 정점과 맞닿아 있는 두 개의 간선 중 가중치가 더 작은 정점
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
간선을 고르면 연결 집합이
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
이러한 방식으로 연결 집합을 확장해나가며 전체 정점을 모두 집합에 포합시킬 때까지 반복한다.
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
프림 알고리즘을 구현할 때는 대체로 간선을 저장하는 우선순위 큐를 생성한다. 연결 집합이 확장될 때마다 새로 맞닿게 되는 간선들을 우선순위 큐에 삽입하고, 연결 집합에 포함할 새로운 정점을 탐색할 때 우선순위 큐에서 차례대로 간선을 꺼내어 사이클 여부를 확인하고 채택하도록 구성한다. 정점의 개수가
구현
인자 형식과 반환 형식은 크루스칼 알고리즘과 동일하다.
import heapq
# edge는 간선 리스트로, 다음과 같은 형태를 띤다.
# edge[m] = (a, b, cost)
def prim(n: int, edge: list[tuple[int, int, int]]) -> list[tuple[int, int, int]]:
result: list[tuple[int, int, int]] = []
edge_list = [[] for _ in range(n)]
for a, b, cost in edge:
edge_list[a].append((b, cost))
edge_list[b].append((a, cost))
connected = [False] * n
connected[0] = True
pq = [(cost, 0, nxt) for nxt, cost in edge_list[0]]
heapq.heapify(pq)
for _ in range(n - 1):
cost: int
a: int
b: int = 0
while connected[b]:
cost, a, b = heapq.heappop(pq)
result.append((a, b, cost))
connected[b] = True
for nxt, cost in edge_list[b]:
if not connected[nxt]:
heapq.heappush(pq, (cost, b, nxt))
return result