六讲贯通C++图的应用之四 最小生成树(1)(2)

Prim算法

如果从顶点入手，就能得到另一种方法。从只含有一个顶点的集合开始，寻找集合外面的顶点到这个集合里的顶点最近的一条边，然后将这个顶点加入集合，修改因为这个顶点的加入而使得集合外面的顶点到集合里的顶点的最短距离产生变化的分量。因为需要对每个顶点扫描，邻接矩阵储存的图是最合适Prim算法的。

template <class name, class dist> int AdjMatrix::MinSpanTree(MSTedge* a)   
{   
dist* lowC = new dist[vNum]; int* nearV = new int[vNum];   
int i, j, k;   
for (i = 0; i < vNum; i++) { lowC[i] = edge[0][i]; nearV[i] = 0; } nearV[0] = -1;   
for (k = 0; k < vNum-1; k++)//Prim Start   
{   
for (i = 1, j = 0; i < vNum; i++)   
if (nearV[i] != -1 && lowC[i] < lowC[j]) j = i;//find low cost   
a[k] = MSTedge(nearV[j], j, lowC[j]); nearV[j] = -1; //insert MST   
if (a[k].cost == NoEdge) return k - 1;//no edge then return   
for (i = 1; i < vNum; i++)//modify low cost   
if (nearV[i] != -1 && edge[i][j] < lowC[i]) { lowC[i] = edge[i][j]; nearV[i] = j; }   
}   
return k;   
}  

【附注】这里需要说明一下，对于edge[I][I]这样的是应该是0呢还是NoEdge呢?显然0合理，但是不好用。并且，从有权图无权图统一的角度来说，是NoEdge更好。因此，在我的有权图的邻接矩阵中，主对角线上的元素是NoEdge，而不是书上的0。

测试程序

储存和操作分离，没想到得到了一个有趣的结果――对于最后的无向图而言，最小生成树的算法对外表现不知道是采用了那个算法。

template <class name, class dist, class mem>   
bool Graph::MinSpanTree()   
{   
MSTedge* a = new MSTedge[vNum() - 1];   
int n = data.MinSpanTree(a); dist sum = dist();   
if (n < vNum() - 1) return false;//不够N－1条边，不是生成树   
for (int i = 0; i < n; i++)   
{   
cout << '(' << getV(a[i].v1) << ',' << getV(a[i].v2) << ')' << a[i].cost << ' ';   
sum += a[i].cost;   
}   
cout << endl << "MinCost: " << sum << endl;   
delete []a;   
return true;   
}  

最后的测试图的数据取自《数据结构算法与应用-C++语言描述》(中文译名)

#include    
using namespace std;   
#include "Graph.h"   
int main()   
{   
Graph<char, int, AdjMatrix<char, int> > a(100);//改为Link储存为Kruskal算法   
a.insertV('A'); a.insertV('B');   
a.insertV('C'); a.insertV('D');   
a.insertV('E'); a.insertV('F');   
a.insertV('G');   
a.insertE('A', 'B', 28); a.insertE('A', 'F', 10);   
a.insertE('B', 'C', 16); a.insertE('C', 'D', 12);   
a.insertE('D', 'E', 22); a.insertE('B', 'G', 14);   
a.insertE('E', 'F', 25); a.insertE('D', 'G', 18);   
a.insertE('E', 'G', 24);   
a.MinSpanTree();   
return 0;   
}