[알고리즘] 최소신장트리(MST) 프림 VS 크루스칼

[알고리즘] 최소신장트리(MST) 프림 VS 크루스칼

728x90

최소신장트리(Minimum Spanning Tree)에 대해 알아보자

MST를 알기위해서는 일단 기본 지식이 필요하다.

기본지식 딱 3가지만 알면된다. "그래프", "트리", "신장트리"

그래프 : 정점과 간선으로 이루어진 네트워크형 자료구조, 사이클이 있을수도있고 없을수도 있음

트리 : 정점과 간선으로 이루어진 계층적 자료구조, 사이클이 있을수도있고 없을수도있음, 루트노드가 있음

신장트리 : 트리의 종류중 하나인데, 모든 정점이 간선으로 연결된 사이클이 없는 트리

이때 신장트리는 트리마다 여러개가 나올 수 있는데, 최소 신장트리는 신장트리들 중에서

간선의 가중치 합이 가장 최소인것을 말한다.

최소신장트리를 찾는방법은 대표적으로 2가지가 있다.

프림 알고리즘 그리고 크루스칼 알고리즘

저 두개의 알고리즘을 알기전에 반드시 지켜야 하는 규칙 2가지를 알고가자.

1. 각 라운드마다 간선은 최소의 가중치를 가진 간선을 선택한다.

2. 사이클이 존재해선 안된다.

3. 정점의 개수가 N개라면 간선의 개수는 N-1개이다.

이제 크루스칼 알고리즘 부터 알아보자.

크루스칼 알고리즘

크루스칼 알고리즘은 간선들의 가중치를 기준으로 오름차순으로 정렬한 뒤

사이클을 만들지 않으면서 간선들을 선택하는 알고리즘이다.

우리같은 사람들은 코드로 이해하는게 더 편하다. 파이썬 코드로 보자.

import sys sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline 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) for i in range(1, v + 1): parent[i] = i edges = [] for i in range(e): a, b, cost = map(int, input().split()) edges.append((cost, a, b)) edges.sort() result = 0 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)

예전에 만들어뒀던 크루스칼 알고리즘 코드이다.

코드대로라면 간선의 cost가 작은 순서대로 알고리즘이 진행되게된다.

다만 크루스칼 알고리즘에서 주의해야할것은 서로소집합 알고리즘을 이용하여 사이클의 여부를 판단한다.

서로소집합 알고리즘에 관한 포스팅은 나중에 진행할것이다.

이제 프림 알고리즘을 보자.

프림 알고리즘

이것도 크루스칼과 거의 비슷하다. 가장 작은 가중치를 가진 간선들만 뽑으면서, 사이클이 없게끔해준다.

그런데 차이점은 트리형태를 유지하면서 간다는것이다.

코드로 보자.

from heapq import heappush, heappop, heapify import sys input = sys.stdin.readline def prim(graph, start): visited[start] = True total_weight, candidate = 0, graph[start] heapify(candidate) while candidate: cost, a, b = heappop(candidate) if not visited[b]: visited[b] = True total_weight += cost for edge in graph[b]: if not visited[edge[2]]: heappush(candidate, edge) return total_weight v, e = map(int, input().split()) graph = [[] for _ in range(v + 1)] visited = [False] * (v + 1) for i in range(e): a, b, cost = map(int, input().split()) graph[a].append([cost, a, b]) graph[b].append([cost, b, a]) print(prim(graph, 1))

heapq(우선순위큐)를 이용하는 코드이다. 우선순위큐말고 sort를 이용해도 무방하긴하다.

저 코드에 나온 방식대로 사용하면 재귀랑 비슷한방식으로 코드가 진행이된다.

결론적으로는 뭐로 하든 상관없지만

시간복잡도를 따지자면 크루스칼은 O(e * log e), 프림은 O(n^2)니깐

기왕이면 크루스칼을 쓰는편이 좋다.

728x90

from http://yuni0822.tistory.com/110 by ccl(A) rewrite - 2021-11-01 17:27:01