数据结构-Prim算法构造无向图的最小生成树

引子：

无向图如果是一个网，那么它的所有的生成树中必有一颗生成树的边的权值之和是最小的，我们称

这颗权值和最小的树为：“最小生成树”（MST）。

其中，一棵树的代价就是树中所有权值之和。

而在现实中，最小生成树的概念可以用来解决很多实际问题，例如，在n个城市之间建立交通网，

那么哪一条路径是最短的呢？就可以用最小生成树来解决。

算法思想：

设G = (V,E)为以连通网，其中V为顶点集合，E为带权边集合。

设置两个新集合U和T：

U用于存放最小生成树的顶点，T用于存放最小生成树的边。

令集合的初值为:{u0}(假设构造最小生成树时，从顶点u0出发。)

集合T的初值为{}。

从所有u∈U，v∈V-U的边（u,v）中，选取最小权值的边（u0,v0），将顶点v0加入集合U中，将边

（u0,v0）加入集合T中。

如此不断重复，知道U = V，最小生成树构造完成，集合T中包含了最小生成树中的所有边。

分析算法可知：

为了实现Prim算法，需要一个辅助数组closedge以记录从U到V-U具有最小代价的边。

对于closedge数组需要包含两个域：

adjvex和lowcost，其中lowcost = 0表示若顶点v不在生成树上，用closedge.lowcost存放v与生成树

上的另一个顶点的序号所构成边的权值。

adjvex存放与该边相关联的生成树上的另一顶点的序号。

算法生成图

对于下面这个无向图例子来说：

算法的执行过程如下：

代码部分：

#include<stdio.h>
#define MAX 100
typedef struct Mgraph{char vertex[MAX];int arcs[MAX][MAX];int vexnum,arcnum;
}Mgraph;typedef struct Closedge{char adjvex[MAX];int lowcost[MAX];
}Closedge;int LocateVerTex(Mgraph *G,char v)
{int k;for(k=0;k<G->vexnum;k++)if(G->vertex[k] == v)return k;return -1;
}void CreateMgraph(Mgraph *G)
{int i,j,weight,adj1,adj2;char v1,v2;printf("请输入顶点数和边数:\n");scanf("%d %d",&G->vexnum,&G->arcnum);getchar();printf("请输入:{%d}个顶点:\n",G->vexnum);for(i=0;i<G->vexnum;i++)scanf("%c",&G->vertex[i]);getchar();printf("请输入:{%d}条边:(格式如下:v1 v2 权值).\n",G->arcnum);for(i=0;i<G->vexnum;i++){for(j=0;j<G->vexnum;j++){G->arcs[i][j] = 9999;}}for(i=0;i<G->arcnum;i++){scanf("%c %c %d",&v1,&v2,&weight);getchar();adj1 = LocateVerTex(G,v1);adj2 = LocateVerTex(G,v2);if(adj1 == -1 || adj2 == -1){printf("失败.\n");i = i - 1;continue;}else{G->arcs[adj1][adj2] = weight;G->arcs[adj2][adj1] = weight;printf("成功.\n");}}
}int MiniNum(Closedge *closedge,Mgraph *G)
{int j,p = 1,min = 999;for(j=0;j<G->vexnum;j++){if(closedge->lowcost[j] != 0 && closedge->lowcost[j] < min){min = closedge->lowcost[j];p = j;}}return p;
}void MiniTree_Prim(Mgraph *G,char u)
{int i,j,k,num;k = LocateVerTex(G,u);Closedge closedge;for(i=0;i<G->vexnum;i++){if(i!=k){closedge.adjvex[i] = u;closedge.lowcost[i] = G->arcs[k][i];}}closedge.lowcost[k] = 0;printf("最小生成树的各条边为:\n");for(i=1;i<G->vexnum;i++){k = MiniNum(&closedge,G);printf("边:<%c,%c>,权值为{%d}:\n",closedge.adjvex[k],G->vertex[k],closedge.lowcost[k]);closedge.lowcost[k] = 0;for(j=0;j<G->vexnum;j++){if(G->arcs[k][j] < closedge.lowcost[j]){closedge.adjvex[j] = G->vertex[k];closedge.lowcost[j] = G->arcs[k][j];}}}
}int main()
{Mgraph G;CreateMgraph(&G);MiniTree_Prim(&G,'A');return 0;
}