/*
Prim's Algorithm, 프림 알고리즘
*/
#include <iostream>
using namespace std;
class Prim
{
private:
typedef struct _graph
{
int v1; //정점 1
int v2; //정점 2
int weight; //가중치
}Graph;
Graph g[20];
int total_edges, total_vertexes; //전체 간선, 정점
int visited[20]; //방문했는가
int temp[20]; //임시로 g[i].weight를 저장하여 min을 찾게 도와주는 배열
public:
Prim()
{
//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;
}
for (int i = 0; i < total_vertexes; i++)
{
visited[i] = 0;
temp[i] = 1000; //말도 안되게 크게 가중치를 잡는다
}
}
void MST()
{
int current = 0, totalVisited = 0, min;
visited[current] = 0;
while (totalVisited != (total_vertexes - 1)) //0부터 시작이므로 정점개수-1
{
for (int i = 0; i < total_vertexes; i++)
{
if (g[i].weight != 0) //가중치가 존재하고
if (visited[i] == 0) //아직 방문하지 않았고
if (temp[i] > g[i].weight)
{
temp[i] = g[i].weight;
}
}
min = 1000; //최소비용을 초기에는 높게 잡아 탐색
for (int i = 0; i < total_vertexes; i++)
{
if (visited[i] == 0) //아직 방문하지 않았다면
if (temp[i] < min) //최소비용 탐색
{
min = temp[i];
current = i;
}
}
visited[current] = 1; //방문했다고 표기
totalVisited++;
}
cout << "MST 출력" << endl;
for (int i = 0; i < total_vertexes; i++)
if (visited[i])
cout << "[" << g[i].v1 << "-" << g[i].v2 << "]" << "\t" << g[i].weight << endl;
}
friend istream &operator>>(istream &is, Prim &p);
};
istream &operator>>(istream &is, Prim &p)
{
cout << "전체 정점 개수 입력: ";
is >> p.total_vertexes;
cout << "전체 간선 개수 입력: ";
is >> p.total_edges;
return is;
}
int main(void)
{
Prim p;
cin >> p;
p.Initialize();
p.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
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
*코드는 기존에 작성한 Kruskal's Algorithm의 형식을 사용해 작성했습니다(추가적으로 visited[i]와 temp[i]를 멤버변수로 추가)