C++의 Prim 알고리즘(인접 행렬 표현을 위한 단순 구현)

프림의 알고리즘 주어진 가중치 무방향 그래프에 대한 최소 스패닝 트리를 찾는 데 사용되는 탐욕적인 방법입니다.

가중 그래프 모든 간선이 가중치 값을 갖는 그래프입니다.

무방향 그래프 모든 모서리가 양방향인 특수한 유형의 그래프입니다.

최소 스패닝 트리 모든 에지와 꼭짓점을 포함하지만 순환은 없고 총 에지 가중치가 가장 적은 부분 ​​집합입니다.

이 글에서는 최소 스패닝 트리를 찾는 프림 알고리즘에 대해 알아볼 것입니다. 일반적으로 알고리즘은 두 개의 배열을 사용하지만 이 솔루션에서는 하나만 사용합니다.

프림 알고리즘의 구현을 보여주는 프로그램.

예시

#include <bits/stdc++.h>
using namespace std;
#define V 5
bool createsMST(int u, int v, vector<bool> inMST){
   if (u == v)
      return false;
   if (inMST[u] == false && inMST[v] == false)
      return false;
   else if (inMST[u] == true && inMST[v] == true)
      return false;
   return true;
}
void printMinSpanningTree(int cost[][V]){
   vector<bool> inMST(V, false);
   inMST[0] = true;
   int edgeNo = 0, MSTcost = 0;
   while (edgeNo < V - 1) {
      int min = INT_MAX, a = -1, b = -1;
      for (int i = 0; i < V; i++) {
         for (int j = 0; j < V; j++) {
            if (cost[i][j] < min) {
               if (createsMST(i, j, inMST)) {
                  min = cost[i][j];
                  a = i;
                  b = j;
               }
            }
         }
      }
      if (a != -1 && b != -1) {
         cout<<"Edge "<<edgeNo++<<" : ("<<a<<" , "<<b<<" ) : cost = "<<min<<endl;
         MSTcost += min;
         inMST[b] = inMST[a] = true;
      }
   }
   cout<<"Cost of Minimum spanning tree ="<<MSTcost;
}
int main() {
   int cost[][V] = {
      { INT_MAX, 12, INT_MAX, 25, INT_MAX },
      { 12, INT_MAX, 11, 8, 12 },
      { INT_MAX, 11, INT_MAX, INT_MAX, 17 },
      { 25, 8, INT_MAX, INT_MAX, 15 },
      { INT_MAX, 12, 17, 15, INT_MAX },
   };
   cout<<"The Minimum spanning tree for the given tree is :\n";
   printMinSpanningTree(cost);
   return 0;
}

출력

The Minimum spanning tree for the given tree is :
Edge 0 : (0 , 1 ) : cost = 12
Edge 1 : (1 , 3 ) : cost = 8
Edge 2 : (1 , 2 ) : cost = 11
Edge 3 : (1 , 4 ) : cost = 12
Cost of Minimum spanning tree =43