/*
Kruskal's Algorithm using disjoint set
집합을 이용한 크루스칼 알고리즘
*/
#include <iostream>
using namespace std;
int Find(int v2, int parent[]) //최종부모 찾기
{
while (parent[v2] != v2)
{
v2 = parent[v2];
}
return v2;
}
void Union(int i, int j, int parent[]) //집합
{
if (i < j)
parent[j] = i; //j의 부모는 i
else
parent[i] = j; //i의 부모는 j
}
class Kruskal
{
private:
typedef struct _graph
{
int v1; //정점 1
int v2; //정점 2
int weight; //가중치
}Graph;
Graph g[20];
int total_edges, total_vertexes; //전체 간선, 정점
public:
Kruskal()
{
//Default
}
void Initialize()
{
cout << "간선과 가중치 입력!" << endl;
for (int i = 0; i < total_edges; i++)
{
cout << "간선 입력(정점 두개를 입력): ";
cin >> g[i].v1 >> g[i].v2;
cout << "간선의 가중치 입력: ";
cin >> g[i].weight;
}
}
int minWeight(int v)
{
int i, min, pos;
min = 1000; //말도 안되게 크게
pos = -1;
for (i = 0; i < v; i++)
{
if (g[i].weight < min)
{
min = g[i].weight;
pos = i;
}
}
return pos;
}
void MST()
{
int count = 0, k = 0, sum = 0, pos;
int v1, v2, v1Parent, v2Parent, tree[10][10], parent[10];
for (int i = 0; i < total_vertexes; i++)
parent[i] = i;
while (count != total_vertexes - 1) //MST에서 간선은 (정점-1)
{
pos = minWeight(total_edges); //가장 작은 가중치를 갖는 간선 찾는다
if (pos == -1) //예외
break;
v1 = g[pos].v1;
v2 = g[pos].v2;
v1Parent = Find(v1, parent);
v2Parent = Find(v2, parent);
if (v1Parent != v2Parent) //같은 부모가 아닐경우(Cycle 배제)
{
tree[k][0] = v1; //배열에 최소간선 저장
tree[k][1] = v2;
k++;
count++;
sum += g[pos].weight;
Union(v1Parent, v2Parent, parent);
}
g[pos].weight = 1000; //더 이상 최소가 아니기 위해 말도 안되게 큰 값으로 초기화
}
if (count == total_vertexes - 1)
{
cout << "\nMST 출력" << endl;
for (int i = 0; i < total_vertexes - 1; i++)
{
int temp1, temp2;
if (tree[i][0] > tree[i][1])
{
temp1 = tree[i][1];
temp2 = tree[i][0];
}
else
{
temp1 = tree[i][0];
temp2 = tree[i][1];
}
cout << "[" << temp1;
cout << "--";
cout << temp2 << "]" << endl;
}
}
else
cout << "\nMST 존재하지 않는다" << endl;
}
friend istream &operator>>(istream &is, Kruskal &k);
};
istream &operator>>(istream &is, Kruskal &k)
{
cout << "전체 정점 개수 입력: ";
is >> k.total_vertexes;
cout << "전체 간선 개수 입력: ";
is >> k.total_edges;
return is;
}
int main(void)
{
Kruskal k;
cin >> k;
k.Initialize();
k.MST();
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서, https://prac-code.blogspot.kr/2013/06/implementation-of-kruskals-algorithm-it.html
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
*코드는 https://prac-code.blogspot.kr/2013/06/implementation-of-kruskals-algorithm-it.html를 대부분 참고해서 작성했습니다.
*보다 쉽게 이해하기 위해 변수명을 바꾸었고 수정한 코드도 있습니다