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

1. 소스 코드

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

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

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

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

구현해야 한다.

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161

#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; }

[직관적인 코드] 

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

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]