최소 신장 트리 - 프림(Prim) 알고리즘

1. 소스 코드

아래 블로그의 설명과 그림을 참조하여 최소 신장 트리 알고리즘 중에 하나인 프림 알고리즘을 구현해 보았다.

우선 순위 큐를 기반으로 구현하였으며, 결과적으로 다른 블로그의 예제와 유사해 보인다.

전체적으로 이해한 바로는 그래프를 너비 우선 순위로 탐색하는 것과 유사하게 구현 뼈대를 가져가고,

단지 Queue에 넣을 때는 일반 Queue가 아닌 우선 순위 큐를 사용하다는 점에 착안하여 구현하는 방향으로

구현해야 한다.

http://swlock.blogspot.kr/2016/02/prim-mstminimum-spanning-tree.html

#include <iostream> #include <vector> #include <queue> #include <functional> struct edgeInfo_t { int from; int to; int weight; }; struct edge_t { int to; int weight; }; const int N = 7; char vtxStr[N] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; bool visited[N]; std::vector<edgeInfo_t> result; auto compare = [](edgeInfo_t a, edgeInfo_t b){ return (a.weight > b.weight); }; using priority_queue_t = std::priority_queue<edgeInfo_t, std::vector<edgeInfo_t>, decltype(compare) >; int getIndex(char ch) { for(int i = 0; i < N; i++) { if(ch == vtxStr[i]) { return i; } } return -1; } void buildGraph(std::vector<edge_t> (&g)[N]) { edgeInfo_t edgeInfo[] = { {getIndex('A'), getIndex('B'), 7}, {getIndex('A'), getIndex('D'), 5}, {getIndex('B'), getIndex('C'), 8}, {getIndex('B'), getIndex('E'), 7}, {getIndex('B'), getIndex('D'), 9}, {getIndex('B'), getIndex('A'), 7}, {getIndex('C'), getIndex('E'), 5}, {getIndex('C'), getIndex('B'), 8}, {getIndex('D'), getIndex('A'), 5}, {getIndex('D'), getIndex('B'), 9}, {getIndex('D'), getIndex('E'), 15}, {getIndex('D'), getIndex('F'), 6}, {getIndex('E'), getIndex('C'), 5}, {getIndex('E'), getIndex('G'), 9}, {getIndex('E'), getIndex('F'), 8}, {getIndex('E'), getIndex('D'), 15}, {getIndex('E'), getIndex('B'), 7}, {getIndex('F'), getIndex('E'), 8}, {getIndex('F'), getIndex('G'), 11}, {getIndex('F'), getIndex('D'), 6}, {getIndex('G'), getIndex('E'), 9}, {getIndex('G'), getIndex('F'), 11}, }; int sz = sizeof(edgeInfo)/sizeof(edgeInfo[0]); for(int i = 0; i < sz; i++) { edge_t edge; int v = edgeInfo[i].from; edge.to = edgeInfo[i].to; edge.weight = edgeInfo[i].weight; g[v].push_back(edge); } } void prim(int sIdx, const std::vector<edge_t> (&g)[N], priority_queue_t &q) { for(int i = 0; i < g[sIdx].size(); i++) { edgeInfo_t edgeInfo; edgeInfo.from = sIdx; edgeInfo.to = g[sIdx][i].to; edgeInfo.weight = g[sIdx][i].weight; q.push(edgeInfo); } visited[sIdx] = true; while(q.empty() == false) { edgeInfo_t edgeInfo = q.top(); int target = edgeInfo.to; q.pop(); if(visited[target] == true) { continue; } visited[target] = true; for(auto v : g[target]) { if(visited[v.to] == false) { edgeInfo_t edgeInfo; edgeInfo.from = target; edgeInfo.to = v.to; edgeInfo.weight = v.weight; q.push(edgeInfo); } } result.push_back(edgeInfo); } } void printGraph(const std::vector<edge_t> (&g)[N]) { for(int i = 0; i < N; i++) { std::printf("Vertex %c : ", vtxStr[i]); for(int j = 0; j < g[i].size(); j++) { std::printf("-> %c ", vtxStr[(g[i][j]).to]); } std::cout << std::endl; } } int main() { std::vector<edge_t> graph[N]; priority_queue_t priorityQ(compare); buildGraph(graph); prim(getIndex('D'), graph, priorityQ); //printGraph(graph); for(auto v : result) { std::printf("%c -> %c [%d]\n", vtxStr[v.from], vtxStr[v.to], v.weight); } return 0; }

[직관적인 코드] 

우선 순위 큐를 사용하지 않고 직관적으로 구현했을 때.

void prim(int sIdx, const std::vector<edge_t> (&g)[N], std::deque<int> &q) { int min = 0x1FFFFFFF; int idx = 0;; bool visited[N]; for(int i = 0; i < N; i++) { visited[i] = false; } q.push_back(sIdx); visited[sIdx] = true; while(q.size() != N) { min = 0x1FFFFFFF; for(auto i : q) { //std::printf("q = %d ", i); for(const auto c : g[i]) { //std::printf("c.to = %d ", c.to); if(visited[c.to] == false) { if(min > c.w) { idx = c.to; min = c.w; //std::printf("idx = %d \n", idx); } } } } q.push_back(idx); visited[idx] = true; } for(auto i : q) { std::printf("%d, %c \n", i, strNode[i]); } }

2. 실행 결과

D -> A [5]

D -> F [6]

A -> B [7]

B -> E [7]

E -> C [5]

E -> G [9]