[Algorithm] Kruskal’s Algorithm
Introduction (including Spanning Tree)
Kruskal 알고리즘이란 최소한의 비용으로 다수의 노드를 연결을 greedy하게 할 때 사용하는 알고리즘이다. 이 알고리즘은 보통 Spanning Tree를 만들 때 사용되는데, Spanning Tree란 graph 구조에서 모든 vertex가 서로 연결이 되는데 최소한의 edge로 연결을 시킨 graph를 말한다. 따라서 Spanning Tree가 되기 위한 조건은 다음과 같다.
총 Vertex의 수 = 총 Edge의 수 + 1
그렇다면 최소한의 비용으로 구성되는 Spanning Tree를 Minimum Spanning Tree (MST)라 부르는데, MST를 만드는 방법을 알아보면 간략하게 다음 과정을 거친다.
Algorithm
- Graph의 edge들을 가중치를 작은 것부터 큰 순서대로 오름차순으로 정렬한다.
- 가장 가중치가 낮은 edge부터 추가하면서 graph를 만든다.
- 만약 edge를 추가하다가 cycle이 발생되면 해당 edge는 제외한다.
- Cycle이 발생되는지 확인 방법은 edge의 source vertex의 그룹과 종료 destination vertex의 그룹이 같으면 cycle이 발생되는 것이라 판단 가능하다.
- Edge의 수가 vertex의 수보다 1개 적으면 종료한다.
Example
![](http://shumin.co.kr/wp/wp-content/uploads/2023/01/image-3-1024x469.png?v=1673532594)
![](http://shumin.co.kr/wp/wp-content/uploads/2023/01/image-4-1024x469.png?v=1673532691)
![](http://shumin.co.kr/wp/wp-content/uploads/2023/01/image-5-1024x469.png?v=1673533019)
![](http://shumin.co.kr/wp/wp-content/uploads/2023/01/image-6-1024x469.png?v=1673533024)
![](http://shumin.co.kr/wp/wp-content/uploads/2023/01/image-7-1024x469.png?v=1673533028)
![](http://shumin.co.kr/wp/wp-content/uploads/2023/01/image-8-1024x469.png?v=1673533032)
![](http://shumin.co.kr/wp/wp-content/uploads/2023/01/image-9-1024x469.png?v=1673533036)
![](http://shumin.co.kr/wp/wp-content/uploads/2023/01/image-10-1024x469.png?v=1673533041)
![](http://shumin.co.kr/wp/wp-content/uploads/2023/01/image-11-1024x469.png?v=1673533045)
Source Code
#include <iostream> #include <vector> #include <algorithm> #define NUM_EDGES 8 #define NUM_VERTEX 5 using namespace std; class Edge { public: Edge(int _src, int _dst, int _w): src(_src), dst(_dst), w(_w) {} int src; int dst; int w; }; vector<Edge> edge_list; int group_table[NUM_VERTEX]; int total_weight; bool cmp(Edge e1, Edge e2) { if (e1.w == e2.w) return e1.src < e2.src; else return e1.w < e2.w; } void addEdge(int _s, int _d, int _w, int _bidirection) { edge_list.push_back(Edge(_s, _d, _w)); } void updateGroupTable(int _s, int _d) { int s_group = group_table[_s]; int d_group = group_table[_d]; int smaller = (s_group < d_group) ? s_group : d_group; int bigger = (s_group < d_group) ? d_group : s_group; for (int i=0; i<NUM_VERTEX; i++) { if (group_table[i] == bigger) group_table[i] = smaller; } } void doMST(void) { int edge_num = 0; for (int i=0; i<NUM_EDGES; i++) { // Compare group number if (group_table[edge_list[i].src] != group_table[edge_list[i].dst]) { printf("[%d]---(%d)---[%d]\n", edge_list[i].src, edge_list[i].w, edge_list[i].dst); edge_num++; total_weight += edge_list[i].w; if (edge_num == NUM_VERTEX + 1) { return; } updateGroupTable(edge_list[i].src, edge_list[i].dst); } } } int main(void) { for (int i=0; i<NUM_VERTEX; i++) group_table[i] = i; addEdge(0, 1, 1, true); addEdge(0, 2, 3, true); addEdge(0, 4, 5, true); addEdge(1, 2, 2, true); addEdge(1, 4, 4, true); addEdge(2, 4, 6, true); addEdge(2, 3, 7, true); addEdge(3, 4, 8, true); sort(edge_list.begin(), edge_list.end(), cmp); doMST(); printf("Total weight: %d\n", total_weight); return 0; }
[0]---(1)---[1] [1]---(2)---[2] [1]---(4)---[4] [2]---(7)---[3] Total weight: 14