가중치 그래프에서 최소 신장 트리(Minimum Spanning Tree, MST)를 구하는 대표적인 방법 중 하나가 바로 크루스칼(Kruskal) 알고리즘입니다. 이 글에서는 크루스칼 알고리즘의 동작 원리, 시간 복잡도, 의사코드, 그리고 실제 C++ 구현 예제까지 단계별로 살펴보겠습니다.
크루스칼 알고리즘이란?
연결 그래프 G(V, E)가 있고, 모든 간선마다 가중치(비용)가 주어져 있다고 가정해 봅시다. 크루스칼 알고리즘은 이 그래프와 비용 정보를 이용해 전체 가중치의 합이 최소가 되는 신장 트리를 찾아냅니다.
이 알고리즘은 트리 병합(tree merging) 방식을 사용합니다. 처음에는 모든 정점이 서로 다른 트리로 존재하며, 알고리즘은 비용이 가장 낮은 간선부터 차례대로 선택해 이 트리들을 하나로 합쳐 최종적으로 하나의 트리를 만듭니다.
동작 원리
먼저 그래프의 모든 간선을 나열한 뒤, 비용을 기준으로 오름차순 정렬합니다. 그다음 정렬된 목록에서 비용이 가장 작은 간선부터 꺼내 트리에 추가하는데, 이때마다 해당 간선이 사이클(cycle)을 형성하는지 검사합니다. 사이클이 생긴다면 그 간선은 버리고 다음 간선으로 넘어갑니다.
- 시간 복잡도는 O(E log E) 또는 O(E log V)입니다. 여기서 E는 간선의 수, V는 정점의 수를 의미합니다.
입출력 예시
입력 – 인접 행렬(adjacency matrix):
0 1 3 4 ∞ 5 ∞
1 0 ∞ 7 2 ∞ ∞
3 ∞ 0 ∞ 8 ∞ ∞
4 7 ∞ 0 ∞ ∞ ∞
∞ 2 8 ∞ 0 2 4
5 ∞ ∞ ∞ 2 0 3
∞ ∞ ∞ ∞ 4 3 0
출력:
Edge: B--A And Cost: 1
Edge: E--B And Cost: 2
Edge: F--E And Cost: 2
Edge: C--A And Cost: 3
Edge: G--F And Cost: 3
Edge: D--A And Cost: 4
Total Cost: 15
알고리즘 (의사코드)
kruskal(g: Graph, t: Tree)
입력 – 주어진 그래프 g와 빈 트리 t
출력 – 선택된 간선들이 담긴 트리 t
Begin
create set for each vertices in graph g
for each set of vertex u do
add u in the vertexSet[u]
done
sort the edge list.
count := 0
while count <= V – 1 do //as tree must have V – 1 edges
ed := edgeList[count] //take an edge from edge list
if the starting vertex and ending vertex of ed are in same set then
merge vertexSet[start] and vertexSet[end]
add the ed into tree t
count := count + 1
done
End
C++ 구현 예제
#include<iostream>
#define V 7
#define INF 999
using namespace std;
//Cost matrix of the graph
int costMat[V][V] = {
{0, 1, 3, 4, INF, 5, INF},
{1, 0, INF, 7, 2, INF, INF},
{3, INF, 0, INF, 8, INF, INF},
{4, 7, INF, 0, INF, INF, INF},
{INF, 2, 8, INF, 0, 2, 4},
{5, INF, INF, INF, 2, 0, 3},
{INF, INF, INF, INF, 4, 3, 0}
};
typedef struct{
int u, v, cost;
}edge;
void swapping(edge &e1, edge &e2){
edge temp;
temp = e1;
e1 = e2;
e2 = temp;
}
class Tree{
int n;
edge edges[V-1]; //as a tree has vertex-1 edges
public:
Tree(){
n = 0;
}
void addEdge(edge e){
edges[n] = e; //add edge e into the tree
n++;
}
void printEdges(){ //print edge, cost and total cost
int tCost = 0;
for(int i = 0; i<n; i++){
cout << "Edge: " << char(edges[i].u+'A') << "--" << char(edges[i].v+'A');
cout << " And Cost: " << edges[i].cost << endl;
tCost += edges[i].cost;
}
cout << "Total Cost: " << tCost << endl;
}
};
class VSet{
int n;
int set[V];//a set can hold maximum V vertices
public:
VSet(){
n = -1;
}
void addVertex(int vert){
set[++n] = vert; //add vertex to the set
}
int deleteVertex(){
return set[n--];
}
friend int findVertex(VSet *vertSetArr, int vert);
friend void merge(VSet &set1, VSet &set2);
};
void merge(VSet &set1, VSet &set2){
//merge two vertex sets together
while(set2.n >= 0)
set1.addVertex(set2.deleteVertex());
//addToSet(vSet1, delFromSet(vSet2));
}
int findVertex(VSet *vertSetArr, int vert){
//find the vertex in different vertex sets
for(int i = 0; i<V; i++)
for(int j = 0; j<=vertSetArr[i].n; j++)
if(vert == vertSetArr[i].set[j])
return i;//node found in i-th vertex set
}
int findEdge(edge *edgeList){
//find the edges from the cost matrix of Graph and store to edgeList
int count = -1, i, j;
for(i = 0; i<V; i++)
for(j = 0; j<i; j++)
if(costMat[i][j] != INF){
count++;
//fill edge list for the position 'count'
edgeList[count].u = i; edgeList[count].v = j;
edgeList[count].cost = costMat[i][j];
}
return count+1;
}
void sortEdge(edge *edgeList, int n){
//sort the edges of graph in ascending order of cost
int flag = 1, i, j;
for(i = 0; i<(n-1) && flag; i++){//modified bubble sort is used
flag = 0;
for(j = 0; j<(n-i-1); j++)
if(edgeList[j].cost > edgeList[j+1].cost){
swapping(edgeList[j], edgeList[j+1]);
flag = 1;
}
}
}
void kruskal(Tree &tr){
int ecount, maxEdge = V*(V-1)/2; //max n(n-1)/2 edges can have in a graph
edge edgeList[maxEdge], ed;
int uloc, vloc;
VSet VSetArray[V];
ecount = findEdge(edgeList);
for(int i = 0; i < V; i++)
VSetArray[i].addVertex(i);//each set contains one element
sortEdge(edgeList, ecount); //ecount number of edges in the graph
int count = 0;
while(count <= V-1){
ed = edgeList[count];
uloc = findVertex(VSetArray, ed.u);
vloc = findVertex(VSetArray, ed.v);
if(uloc != vloc){ //check whether source abd dest is in same set or not
merge(VSetArray[uloc], VSetArray[vloc]);
tr.addEdge(ed);
}
count++;
}
}
int main(){
Tree tr;
kruskal(tr);
tr.printEdges();
}
실행 결과
Edge: B--A And Cost: 1
Edge: E--B And Cost: 2
Edge: F--E And Cost: 2
Edge: C--A And Cost: 3
Edge: G--F And Cost: 3
Edge: D--A And Cost: 4
Total Cost: 15
마무리
크루스칼 알고리즘은 간선을 비용 순으로 정렬한 뒤, 사이클을 형성하지 않는 간선만 골라 트리를 확장해 나가는 직관적이고 강력한 MST 알고리즘입니다. 위 예제에서는 집합(set)을 이용해 두 정점이 같은 집합에 속하는지 확인함으로써 사이클 생성 여부를 판단했습니다. 실무에서는 이 과정을 더 효율적으로 처리하기 위해 유니온-파인드(Union-Find, 서로소 집합) 자료구조를 함께 사용하는 것이 일반적입니다.