#include <iostream>
using namespace std;
const int MAXVEX=100;
int lowcost[MAXVEX]; /*lostcost用来表示该顶点是否已经被选入生成树中和权值,若为0,则被选入生成树*/
int adj[MAXVEX]; /*adj是用来记录adj[坐标]的前驱顶点*/
const int INFINITY=32767; //设置无穷大
typedef struct /*含有邻接矩阵的图*/
{
int vertex[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes,numEdges;
}MGraph;
void CreateGraph(MGraph *G) /*创建图*/
{
cout<<"请输入图的顶点数与边数:"<<endl;
cin>>G->numVertexes>>G->numEdges;
for(int i=0;i<G->numVertexes;i++)
{
for(int j=0;j<G->numVertexes;j++)
{
G->arc[i][j]=0;
G->arc[i][j]=INFINITY;/*图的邻接矩阵的初始化是让它们都是无穷大,再给相连通路添相应权值*/
}
}
for(int i=0;i<G->numVertexes;i++) /*存放顶点表信息*/
G->vertex[i]=0;
cout<<"输入各顶点"<<endl;
for(int i=0;i<G->numVertexes;i++)
cin>>G->vertex[i];
for(int i=0;i<G->numEdges;i++) /*根据图构建邻接矩阵*/
{
int m,n;
cout<<"请输入边的两个顶点所在下标:"<<endl;
cin>>m>>n;
cout<<"输入边的权值"<<endl;
cin>>G->arc[m][n];
G->arc[n][m]=G->arc[m][n];
}
}
void Prim(MGraph *G) /*最小生成树算法:普利姆算法*/
{
for(int i=0;i<G->numVertexes;i++) /*初始顶点0作为最小生成树的起始顶点,0到各点的距离为lostcost[]*/
{
lowcost[i]=0;
adj[i]=0;
lowcost[i]=G->arc[0][i];
}
for(int i=0;i<G->numVertexes;i++) /*主循环*/
{
int min=INFINITY;
int k=0;
for(int j=1;j<G->numVertexes;j++) /*寻找顶点0到最近距离的顶点*/
{
if(lowcost[j]!=0&&lowcost[j]<min)
{k=j;
min=lowcost[j];
}
}
lowcost[k]=0; /*将k顶点纳入生成树集合*/
cout<<adj[k]<<'\t'<<k<<endl;
for(int x=1;x<G->numVertexes;x++)/*在新加入的顶点中寻找到某点最短的距离,并且邻接点未加入生成树*/
{
if(lowcost[x]!=0&&G->arc[k][x]<lowcost[x])
{
lowcost[x]=G->arc[k][x];
adj[x]=k;
}
}
}
}
int main()
{
MGraph *G=new MGraph; /*new图*/
CreateGraph(G); /*构建图*/
for(int i=0;i<G->numVertexes;i++)
{
for(int j=0;j<G->numVertexes;j++)
cout<<G->arc[i][j]<<endl;
}
Prim(G); /*普利姆算法*/
return 0;
}
普利姆算法的流程图:
普利姆算法实例:
普利姆算法实例结果:
普利姆算法核心:
是将图中的所有顶点全部选出,但是是以某个顶点为起点。选点规则是:在已选出的点中选出距离最近并且未选出的点。如此往复,选光所有点为止。