모든 간선에 가중치(비용)가 부여된 연결 그래프 G(V, E)가 주어졌을 때, 크루스칼(Kruskal) 알고리즘은 이 그래프에서 최소 신장 트리(Minimum Spanning Tree, MST)를 찾아냅니다.
이 알고리즘은 병합 트리(merge-tree) 방식에 기반합니다. 처음에는 각 정점이 독립적인 트리로 존재하며, 알고리즘은 비용이 가장 작은 간선부터 선택해 이 트리들을 점차 하나의 트리로 병합해 나갑니다.
동작 원리
크루스칼 알고리즘은 다음 순서로 진행됩니다.
- 그래프의 모든 간선을 비용 기준으로 오름차순 정렬합니다.
- 정렬된 목록에서 비용이 가장 작은 간선부터 차례로 꺼냅니다.
- 해당 간선을 트리에 추가했을 때 사이클(cycle)이 형성되는지 검사합니다.
- 사이클이 생기면 그 간선은 버리고 다음 간선으로 넘어갑니다.
- 간선이 V-1개가 될 때까지 반복합니다.
시간 복잡도
이 알고리즘의 시간 복잡도는 O(E log E) 또는 O(E log V)입니다. 여기서 E는 간선의 수, V는 정점의 수를 의미합니다.
입력과 출력
입력: 인접 행렬(Adjacency Matrix) 출력: 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 //트리는 반드시 V – 1개의 간선을 가져야 함
ed := edgeList[count] //간선 목록에서 간선 하나를 꺼냄
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
EndC++ 구현 예제
#include<iostream>
#define V 7
#define INF 999
using namespace std;
//그래프의 비용 행렬(Cost matrix)
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]; //트리는 정점 수 - 1개의 간선을 가짐
public:
Tree() {
n = 0;
}
void addEdge(edge e) {
edges[n] = e; //트리에 간선 e 추가
n++;
}
void printEdges() { //간선, 비용, 총 비용 출력
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]; //하나의 집합은 최대 V개의 정점을 저장 가능
public:
VSet() {
n = -1;
}
void addVertex(int vert) {
set[++n] = vert; //집합에 정점 추가
}
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) {
//두 정점 집합을 병합
while(set2.n >= 0)
set1.addVertex(set2.deleteVertex());
}
int findVertex(VSet *vertSetArr, int vert) {
//여러 정점 집합 중에서 해당 정점 찾기
for(int i = 0; i<V; i++)
for(int j = 0; j<=vertSetArr[i].n; j++)
if(vert == vertSetArr[i].set[j])
return i; //i번째 정점 집합에서 노드 발견
}
int findEdge(edge *edgeList) {
//그래프의 비용 행렬에서 간선을 찾아 edgeList에 저장
int count = -1, i, j;
for(i = 0; i<V; i++)
for(j = 0; j<i; j++)
if(costMat[i][j] != INF) {
count++;
//'count' 위치에 간선 목록 채우기
edgeList[count].u = i; edgeList[count].v = j;
edgeList[count].cost = costMat[i][j];
}
return count+1;
}
void sortEdge(edge *edgeList, int n) {
//그래프의 간선을 비용 오름차순으로 정렬
int flag = 1, i, j;
for(i = 0; i<(n-1) && flag; i++) { //개선된 버블 정렬 사용
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; //그래프는 최대 n(n-1)/2개의 간선을 가질 수 있음
edge edgeList[maxEdge], ed;
int uloc, vloc;
VSet VSetArray[V];
ecount = findEdge(edgeList);
for(int i = 0; i < V; i++)
VSetArray[i].addVertex(i); //각 집합은 하나의 원소만 포함
sortEdge(edgeList, ecount); //그래프 내 간선 수는 ecount개
int count = 0;
while(count <= V-1) {
ed = edgeList[count];
uloc = findVertex(VSetArray, ed.u);
vloc = findVertex(VSetArray, ed.v);
if(uloc != vloc) { //출발점과 도착점이 같은 집합에 있는지 검사
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