Computer >> 컴퓨터 >  >> 프로그램 작성 >> 프로그램 작성

Prim의 최소 스패닝 트리 알고리즘


연결된 그래프 G(V, E)가 있고 모든 모서리에 대한 가중치 또는 비용이 제공됩니다. Prim의 알고리즘은 그래프 G에서 최소 스패닝 트리를 찾습니다.

그것은 성장하는 나무 접근 방식입니다. 이 알고리즘은 트리를 시작하기 위해 시드 값이 필요합니다. 시드 정점이 성장하여 전체 트리를 형성합니다.

Prim의 최소 스패닝 트리 알고리즘

문제는 두 세트를 사용하여 해결됩니다. 한 세트는 이미 선택된 노드를 보유하고 다른 세트는 아직 고려되지 않은 항목을 보유합니다. seed vertex에서 최소 edge cost를 기준으로 인접한 vertex를 취하므로 노드를 하나씩 취하여 트리를 성장시킵니다.

이 문제의 시간 복잡도는 O(V^2)입니다. 여기서 V는 정점의 수입니다.

입력 및 출력

Input:
The adjacency list:
Prim의 최소 스패닝 트리 알고리즘 
Output:
(0)---(1|1)  (0)---(2|3)  (0)---(3|4)
(1)---(0|1)  (1)---(4|2)
(2)---(0|3)
(3)---(0|4)
(4)---(1|2)  (4)---(5|2)
(5)---(4|2)  (5)---(6|3)
(6)---(5|3)

알고리즘

prims(g: Graph, t: tree, start)

입력 - 그래프 g, 빈 트리 및 'start'라는 이름의 시드 정점

출력 - 가장자리를 추가한 후의 트리입니다.

Begin
   define two sets as usedVert, unusedVert
   usedVert[0] := start and unusedVert[0] := φ

   for all vertices except start do
      usedVert[i] := φ
      unusedVert[i] := i    //add all vertices in unused list
   done

   while number of vertices in usedVert ≠ V do    //V is number of total nodes
      min := ∞
      for all vertices of usedVert array do
         for all vertices of the graph do
            if min > cost[i,j] AND i ≠ j then
               min := cost[i,j]
               ed := edge between i and j, and cost of ed := min
         done
      done

      unusedVert[destination of ed] := φ
      add edge ed into the tree t
      add source of ed into usedVert
   done
End

#include<iostream>
#define V 7
#define INF 999
using namespace std;

//Cost matrix of the graph
int costMat[V][V] = {
   {0, 1, 3, 4, INF, 5, INF},
   {1, 0, INF, 7, 2, INF, INF},
   {3, INF, 0, INF, 8, INF, INF},
   {4, 7, INF, 0, INF, INF, INF},
   {INF, 2, 8, INF, 0, 2, 4},
   {5, INF, INF, INF, 2, 0, 3},
   {INF, INF, INF, INF, 4, 3, 0}
};

typedef struct {
   int u, v, cost;
}edge;

class Tree {
   int n;
   edge edges[V-1];    //as a tree has vertex-1 edges
   public:
      Tree() {
         n = 0;
      }

      void addEdge(edge e) {
         edges[n] = e;    //add edge e into the tree
         n++;
      }

      void printEdges() {    //print edge, cost and total cost
         int tCost = 0;

         for(int i = 0; i<n; i++) {
            cout << "Edge: " << char(edges[i].u+'A') << "--" << char(edges[i].v+'A');
            cout << " And Cost: " << edges[i].cost << endl;
            tCost += edges[i].cost;
         }
         cout << "Total Cost: " << tCost << endl;
      }
      friend void prims(Tree &tre, int start);
};

void prims(Tree &tr, int start) {
   int usedVert[V], unusedVert[V];
   int i, j, min, p;
   edge ed;

   //initialize
   usedVert[0] = start; p = 1;
   unusedVert[0] = -1;    //-1 indicates the place is empty

   for(i = 1; i<V; i++) {
      usedVert[i] = -1;    //all places except first is empty
      unusedVert[i] = i;   //fill with vertices
   }

   tr.n = 0;
   //get edges and add to tree
   while(p != V) {     //p is number of vertices in usedVert array
      min = INF;
      for(i = 0; i<p; i++) {
         for(j = 0; j<V; j++) {
            if(unusedVert[j] != -1) {
               if(min > costMat[i][j] && costMat[i][j] != 0) {
                  //find the edge with minimum cost
                  //such that u is considered and v is not considered yet
                  min = costMat[i][j];
                  ed.u = i; ed.v = j; ed.cost = min;
               }
            }
         }
      }
      unusedVert[ed.v] = -1;     //delete v from unusedVertex
      tr.addEdge(ed);
      usedVert[p] = ed.u; p++;   //add u to usedVertex
   }
}

main() {
   Tree tr;
   prims(tr, 0);    //starting node 0
   tr.printEdges();
}

출력

(0)---(1|1)  (0)---(2|3)  (0)---(3|4)
(1)---(0|1)  (1)---(4|2)
(2)---(0|3)
(3)---(0|4)
(4)---(1|2)  (4)---(5|2)
(5)---(4|2)  (5)---(6|3)
(6)---(5|3)