Prim的最小生成树算法

有一个连通图G(V,E)并给出了每个边的权重或成本。Prim的算法将从图G中找到最小生成树。 

这是一种成长中的树方法。该算法需要种子值来启动树。种子顶点长成整棵树。

该问题将通过两组解决。一组保存已选择的节点，另一组保存尚未考虑的项目。从种子顶点开始，它基于最小的边沿代价获取相邻的顶点，因此，它通过逐个获取节点来生长树。

此问题的时间复杂度为O（V ^ 2）。这里V是顶点数。

输入输出

Input:
The adjacency list: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;

//图的成本矩阵
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 << " 和费用： " << edges[i].cost << endl;
            tCost += edges[i].cost;
         }
         cout << "总费用： " << 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;

   //初始化
   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;
   //获得边缘并添加到树
   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) {
                  //以最低的成本找到优势
                  //这样就考虑了u而尚未考虑v-
                  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)