[MST] Kruskal's Algorithm & Prim's Algorithm

1. 개요

잊어버리기 쉬운 알고리즘인 Kruskal's Algorithm과 Prim's Algorithm에 대해서 공부해 보는 시간을 가졌다.

두 알고리즘은 Minimum Spanning Tree를 해결하기 위한 대표적인 두 알고리즘이다.

 

Kruskal's Algorithm은 edge가 제일 작은 값들 순으로 접근하여, 해당 edge를 잇는 정점 u, v의 parent node가 동일하지 않다면 합쳐주는 방법이다. - parent node가 동일한데, 해당 edge를 포함시키게 되면 cycle을 형성하게 될 것이기 때문이다.

 

Prim's Algorithm은 edge가 아닌, node를 기준으로 접근하는 방법이다.

일단, 특정 node를 선택하고, 해당 노드가 접근할 수 있는 노드까지의 weight 중 가장 작은 weight를 가진 node를 선택하도록 하는 방법이다. node를 선택하는 기준은 key list가 관여하게 된다.

특정 노드를 선택하여 접근할 때마다, 해당 노드에서 모든 노드로의 weight를 계산하고, 현재 지니고 있는 weight 보다 작다면, key[index] 값을 작은 weight 값으로 변경시켜 준다. 0이면 해당 노드에 접근 불가하기 때문에, 포함시키지 않는다.

 

 

2. Kruskal's Algorithm

https://www.geeksforgeeks.org/kruskals-algorithm-in-python/

Kruskal's Algorithm in Python - GeeksforGeeks

 

역시 geeksforgeeks... 아주 좋은 정석 코드를 알려주어, 이해하기가 좋다.

 

kruskal's Algorithm은 minimum spanning tree에 대한 solution 중 하나로, greedy Algorithm 에 속한다.

greedy Algorithm은 탐욕스러운 알고리즘으로 현재 상황에서 최선의 경우를 선택해서 나아가는 경우를 의미한다.

 

u, v, weight 값을 graph에 포함시켜서 시작해 준다.

 

즉, weight 중 가장 작은 간선을 골라 부모 노드를 확인하고, 일치하지 않는다면 result에 append 하는 방식으로 진행이 된다.

 

부모 노드의 일치 유무를 확인하는 이유는, 부모 노드가 동일 하다면 cycle을 형성할 것이기 때문이다.

parent list는 부모 노드의 일치 여부를 확인하기 위해 존재하며, rank list는 각 노드 당 rank를 결정해 두어, 부모 노드를 선택할 수 있는 우선순위를 제공하기 위함이다. 

만약 입력된, 2개의 노드의 rank 가 동일하다면, 하나의 노드에 다른 노드의 부모 노드의 값을 넣어주고, 하나의 rank + 1을 하는 방식으로 올려준다.

 

3. Prim's Algorithm 

https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/

Prim’s Algorithm for Minimum Spanning Tree (MST) - GeeksforGeeks

 

역시나~ 정석 코드를 제공해 주는 Prim's Algorithm을 참고하였다.

prim's Algorithm은 2차원 배열로 u, v로의 weight를 저장하게 된다.

부모 노드를 저장해 놓는 Parent list, 방문 여부를 포함히기 위한 visited list, 그리고 우선 순위를 나타내기 위한 key list를 만들어 놓았다.

 

sys.maxsize를 통해서, 가장 큰 값을 넣어주어 가장 낮은 weight를 가진 이를 선택할 수 있도록 하였다.

초기에는 무작위 vertex를 선택해 주고 알고리즘을 시작해야 한다. 대게 0을 선택하여 진행한다.

 

가장 작은 vertex를 선택하였다면, 해당 vertex로 방문할 수 있는 다른 vertex에 대해서 visited가 False고, 0 보다 큰 값을 가지고 있으며, 현재 저장되어 있는 key[index] 보다 작다면, key[index] 값과 parent[index] 값을 update 해주었다.

 

4. Kruskal's Algorithm vs. Prim's Algorithm

https://velog.io/@jjhjjh1159/%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%B9%BC-VS-%ED%94%84%EB%A6%BC-%ED%8C%8C%ED%97%A4%EC%B9%98%EA%B8%B0-pzljatpq

크루스칼 VS 프림 파헤치기

 

https://ongveloper.tistory.com/376

[알고리즘] 크루스칼(Kruskal)과 프림(Prim)

 

Kruskal's 알고리즘의 경우 edge들을 오름차순 정렬을 해야하기에 O(ElogE)의 값이 소모된다.

반면 Prim's 알고리즘의 경우

1. 인접 행렬의 경우 O(v**2) 의 시간 복잡도를,
2. min heap을 이용할 경우O(ElogV)의 시간 복잡도를 지니게 된다. (vertex들이 최소 힙에 들어갔다가 나오는 경우)