图的最小生成树，就是基于图，假设其有n的顶点，那么就要构建一颗连通树，使其各边权重和最小。最小生成树的实现算法主要有两种：Prim算法和Kruskal算法。本文着重介绍Prim算法及其实现，其中图的实现以及相关操作，采用前面博文C++ 图的实现中的实现方式，由于本文重点在于Prim算法的实现，所有就不在图的构建以及相关操作中过多赘述。
首先来看Prim算法，维基的解释其实已经很详细了，算法思想很好理解，不多说明，直接看实现。
/*
*无向图查找最小树：Prim算法
*不断找已知顶点邻接边中的最小值，在不形成环的前提下，加入边
*----- By F8Master
*/
#include "Graphmtx.h"
#include<iostream>
#include<vector>
using namespace std;
struct EdgeByInt
{
int v1,v2;
EdgeByInt(){};
EdgeByInt (int v11,int v22){
v1 = v11;
v2 = v22;
}
};
template<class T ,class E>
void Prim(Graphmtx<T,E> &G,vector<EdgeByInt> &v)//参数分别为图G，存储最小树的边的vector v
{
int numV = G.NumberOfVertices();//顶点数
int *setV = new int[numV];//表明所在集合的
for(int i = 0;i<numV;i++)//setV初始化为本身，当已经访问过之后，会更改其值为-1
setV[i] = i;
v.clear();
vector<int> vvertex(numV);//存已分配好了的点
vvertex.push_back(0);
setV[0] = -1;//凡是分配好的点均被设置为-1，以示区别
int j = 0;//找到的边的数目
while( j < numV - 1)
{
E min = INF;
int left = -1;
int right = -1;
for(int n = 0;n<vvertex.size();n++)//找到已知集里面点的邻接最近点
{
for (int m = 0;m<numV;m++)
{
if(m!=n && setV[m] != -1 &&G.getWeight(vvertex[n],m)<min )
{
min = G.getWeight(vvertex[n],m);
left = vvertex[n];
right = m;
}
}
}
setV[right] = -1;
vvertex.push_back(right);
EdgeByInt temp(left,right);
v.push_back(temp);
j++;
}
}
template <class T ,class E>
void printMinTree(Graphmtx<T,E> & G,vector<EdgeByInt> &v)
{
int size = v.size();
EdgeByInt temp;
int left,right;
for(int i = 0;i<size;i++)
{
temp = v[i];
left = v[i].v1;
right = v[i].v2;
cout<<"("<<G.getValue(left)<<" , "<<G.getValue(right)<<")"<<endl;
}
};
//测试程序
void test_Prim()
{
Graphmtx<char,int> G ;
G.inputGraph();
vector<EdgeByInt> v(G.NumberOfEdges()-1);
Prim(G,v);
printMinTree(G,v);
} 简单的测试程序：
- 对于下图，执行程序得到结果：
- 对于下图，执行测试：
