最小生成树（Prim算法）代码实现
#include<iostream>
#include<>
using namespace std;
#define MaxVertexNum 100
#define INFINITY 30000
typedef struct{
int adjVertex; //某定点与已构造好的部分生成树的顶点之间权值最小的顶点
int lowCost; //某定点与已构造好的部分生成树的顶点之间的最小权值。
}CloseEdge; //辅助数组
typedef int EdgeType; //边的数据类型
typedef struct{
int Vex[MaxVertexNum]; //定点表
EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表,
//存放边的权值，如果为Edge[i][j]=INFINITY，则表示顶点i,j之间无边
int vernum,arcnum; //图的当前顶点数和弧数
}MGraph; //适合存储稠密图
//邻接矩阵法创建一个图
void CreateMGraph(MGraph *G)
{
int i,j,k,w;
printf("请输入图的顶点数和边数：");
cin>>G->vernum>>G->arcnum;
printf("请输入图的各个顶点的信息（A,B…）：");
for(i=0;i<G->vernum;i++)
cin>>G->Vex[i];//"%c"中%c后面要有空格
for(i=0;i<G->vernum;i++)
{
for(j=0;j<G->vernum;j++)
G->Edge[i][j]=INFINITY;
}
printf("请输入各条边的信息（例：1 2表示在A顶点和B顶点之间有一条边）:\n");
for(k=0;k<G->arcnum;k++)
{//此为创建有向图的邻接矩阵
int Iindex,Jindex,weight;
cin>>Iindex>>Jindex>>weight;
G->Edge[Iindex][Jindex]=weight;
//如果加上G->Edge[j][i]=1;则建立的是无向图的邻接矩阵
G->Edge[Jindex][Iindex]=weight;
}
}
//输出图的邻接矩阵
void DisplayMGraph(MGraph G)
{
int i,j;
printf(" ");
for(i=0;i<G.vernum;i++)
printf("%d ",G.Vex[i]);
for(i=0;i<G.vernum;i++)
{
printf("\n%d\t",G.Vex[i]);
for(j=0;j<G.vernum;j++)
printf("%d ",G.Edge[i][j]);
}
}
//Prim算法求最小生成树
void MinSpanTree_PRIM(MGraph G,int u,CloseEdge closeEdge[])
{//从第u个顶点出发构造图G的最小生成树，最小生成树顶点信息存放在
//数组closeEdge中
int i,j,w,minindex,LowCost=0;
for(i=0;i<G.vernum;i++)
if(!u)
{
closeEdge[i].adjVertex=u;
closeEdge[i].lowCost=G.Edge[u][i];
}
closeEdge[u].lowCost=0; /*初始，U={u}*/
for(i=0;i<G.vernum-1;i++)/*选择加入其余-1个结点*/
{
w=INFINITY;
for(j=0;j<G.vernum;j++)/*在辅助数组closeEdge中选取权值最小的顶点*/
{
if(closeEdge[j].lowCost!=0&&closeEdge[j].lowCost<w)
{
w=closeEdge[j].lowCost;
minindex=j;
}
}
LowCost+=w;//将最小边权值加入最小代价
closeEdge[minindex].lowCost=0; /*将第minindex顶点并入U集*/
for(j=0;j<G.vernum;j++)/*新顶点并入U后，修改辅助数组*/
{
if(G.Edge[minindex][j]<closeEdge[j].lowCost)
{
closeEdge[j].adjVertex=minindex;
closeEdge[j].lowCost=G.Edge[minindex][j];
}
}
}
printf("生成树的各边为：\n");
for(i=0;i<G.vernum;i++)/*打印最小生成树的各条边*/
{
if(i!=u)
printf("\n%d->%d,%d",i,closeEdge[i].adjVertex,G.Edge[i][closeEdge[i].adjVertex]);
}
printf("\n构造生成树的总代价为：%d\n",LowCost);
}
int main()
{
MGraph G;
CloseEdge closeEdge[MaxVertexNum];
CreateMGraph(&G);
DisplayMGraph(G);
MinSpanTree_PRIM(G,0,closeEdge);
return 0;
}