C语⾔-最⼩⽣成树（Prim算法）
1. 查函数（LocateVex查坐标）
2. 构建⽆向⽹（Undirected Network）
3. 输出邻接矩阵（print）
4. 最⼩值函数（minimal）
5. 普⾥姆算法（MiniSpanTree_Prim）
最⼩代价⽣成树背景
2假设在n个城市之间建⽴铁路⽹，在每两个城市之间都可设置⼀条线路，每条线路对应要付出的代价不同，n个城市之间最多可⽣成(n-n)/2条线路，我们如何设计线路才能⽤最少的路径（最少要n-1条）最低的成本架设完这些铁路线路？
即使我们⽤最少的线路，即n-1条线路来贯穿n个城市，结果不唯⼀，付出的总代价也不唯⼀，我们将每⼀个结果称作⽣成树，⽽总花费最少的我们称作最⼩代价⽣成树（Minimum Cost Spanning Tree），简称最⼩⽣成树。
MST性质及理解
MST性质定义：设G=(V，E)是⼀个连通⽹，U是顶点集V的⼀个真⼦集。若(u，v)是G中⼀条具有最⼩权值的边，其中u∈U,v∈V-U，则⼀定存在G的⼀棵最⼩⽣成树包括此边(u，v)。
直⽩的意思就是说：整个图（⽹）G中权值最⼩的边⼀定会是最⼩⽣成树的边。
如何理解呢？其实我们可以将问题简化⼀点，假设图G有3个顶点三条边,AB、AC和BC，权值分别为3、4、5，那么此时在这个简单图中的最⼩⽣成树肯定会包含权值为3的AB。因为A结点在选择AB或AC的时候会选权值⼩代价低的那个。
那么这下我们也就明⽩了，其实这个MST也就是——贪⼼算法，选择当前情况下的最优解，即对应了MST中选择代价最⼩的。当顶点A
在选择的时候，只能选择A-B或A-C，那么A-B的代价更⼩，故选择A-B。这就是MST性质。
普⾥姆算法（Prim） 和 克鲁斯卡尔算法（Kruskal） 均是基于MST性质。
最⼩⽣成树算法：
1. 普⾥姆算法（Prim）：对顶点操作，在最⼩⽣成树的顶点集U和待处理顶点集V-U中，不断地寻最短边(代价最⼩变)，到后将对应
顶点加⼊集合U，直到所有顶点均处理完毕(V-U⾥没有剩余顶点)
2. ）：对边操作，每次选取⼀条最短边，如果不会和当前最⼩⽣成树构成环（回路），将此最短边加⼊最⼩⽣成树中。当选取了n-1（顶
点数-1）条边，或出了所有符合条件的不成环边最⼩⽣成树⽣成完毕。
普⾥姆算法：
普⾥姆算法其实是在U和V-U两个阵营中不停的⼀条最短的（代价最低的）可连通的边，然后将该边附着的在V-U阵营中的顶点加⼊U
阵营中Array
如何⽤程序实现Prim算法
1. ⾸先我们需要⼀个结构体数组：最短路径数组shortedge来存储当前各个顶点之间的最短路径信息，其中的adjvex⽤于存储最短边的
邻接点，lowcost是其对应权值，也就是当前最⼩的代价。
typedef struct//最短路径数组结构体(候选最短边)
{
VertexType adjvex;//候选最短边的邻接点
int lowcost;//候选最短边的权值
}ShortEdge;
2.
2.1 对起始点start处理：
① 对shortedge数组写⼊初始化信息
② 将起始点放⼊集合U中，即 shortedge[k].lowcost=0;//lowcost为0表⽰该顶点属于U集合
2.2 对后续顶点进⾏处理：
① 通过minimal函数到最⼩路径所对应的的顶点
② 输出最⼩路径信息
③ 将此路径对应的顶点放⼊集合U中（将其对应的lowcost改为0）
④ 更新shortedge数组（集合U中加⼊新的顶点，阵营U中有可能⽣成新的最⼩路径到达阵营V-U中）
void MiniSpanTree_Prim(MGraph *G,VertexType start)
{
int i,j,k;
ShortEdge shortedge[VertexMax];
//1.处理起始点start
k=LocateVex(G,start);
for(i=0;i<G->vexnum;i++)
{
shortedge[i].adjvex=start;
shortedge[i].lowcost=G->AdjMatrix[k][i];
}
shortedge[k].lowcost=0;//lowcost为0表⽰该顶点属于U集合
//2.处理后续结点
for(i=0;i<G->vexnum-1;i++)//对集合U，去最短路径的顶点
{
k=minimal(G,shortedge);//最短路径的顶点
printf("%c->%c,%d\n",shortedge[k].adjvex,G->Vertex[k],shortedge[k].lowcost);//输出到的最短路径顶，及路径权值
shortedge[k].lowcost=0;//将到的最短路径顶点加⼊集合U中
for(j=0;j<G->vexnum;j++)//U中加⼊了新节点，可能出现新的最短路径，故更新shortedge数组
{
if(G->AdjMatrix[k][j]<shortedge[j].lowcost)//有更短路径出现时，将其替换进shortedge数组
{
shortedge[j].lowcost=G->AdjMatrix[k][j];
shortedge[j].adjvex=G->Vertex[k];
}
}
}
}
3. 求最⼩值的函数（minimal）：只需要在当前shortage数组中⽐较出lowcost最⼩的元素，返回它的下标loc即可在Vertex数组中到
该元素。
完整源代码
#include<stdio.h>
#include<stdlib.h>
#define VertexMax 20 //最⼤顶点数为100
#define MaxInt 32767 //表⽰最⼤整数，表⽰ ∞
typedef char VertexType;//每个顶点数据类型为字符型
typedef struct//邻接矩阵结构体
{
VertexType Vertex[VertexMax];//存放顶点元素的⼀维数组
int AdjMatrix[VertexMax][VertexMax];//邻接矩阵⼆维数组
int vexnum,arcnum;//图的顶点数和边数
}MGraph;
typedef struct//辅助数组结构体(候选最短边)
{
VertexType adjvex;//候选最短边的邻接点
int lowcost;//候选最短边的权值
}ShortEdge;
int LocateVex(MGraph *G,VertexType v)//查元素v在⼀维数组 Vertex[] 中的下标，并返回下标{
int i;
for(i=0;i<G->vexnum;i++)
{
if(v==G->Vertex[i])
{
return i;
}
}
printf("No Such Vertex!\n");
return-1;
}
void CreateUDN(MGraph *G)//构建⽆向⽹（Undirected Network）
{
int i,j;
/
/1.输⼊顶点数和边数
printf("输⼊顶点个数和边数：\n");
printf("顶点数 n=");
scanf("%d",&G->vexnum);
printf("边数 e=");
scanf("%d",&G->arcnum);
printf("\n");
printf("\n");
//2.输⼊顶点元素
printf("输⼊顶点元素(⽆需空格隔开)：");
scanf("%s",G->Vertex);
printf("\n");
//3.矩阵初始化
for(i=0;i<G->vexnum;i++)
for(j=0;j<G->vexnum;j++)
{
G->AdjMatrix[i][j]=MaxInt;
}
//4.构建邻接矩阵
int n,m;
VertexType v1,v2;
int w;//v1->v2的权值
printf("请输⼊边的信息和权值(例：AB,15)：\n");
for(i=0;i<G->arcnum;i++)
{
printf("输⼊第%d条边信息及权值：",i+1);
scanf(" %c%c,%d",&v1,&v2,&w);
n=LocateVex(G,v1);//获取v1所对应的在Vertex数组中的坐标
m=LocateVex(G,v2);//获取v2所对应的在Vertex数组中的坐标
if(n==-1||m==-1)
{
printf("NO This Vertex!\n");
return;
G->AdjMatrix[n][m]=w;
G->AdjMatrix[m][n]=w;//⽆向⽹仅此处不同
}
}
void print(MGraph G)
{
int i,j;
printf("\n-------------------------------");
printf("\n 邻接矩阵：\n\n");
printf("\t ");
for(i=0;i<G.vexnum;i++)
printf("\t%c",G.Vertex[i]);
printf("\n");
for(i=0;i<G.vexnum;i++)
{
printf("\t%c",G.Vertex[i]);
for(j=0;j<G.vexnum;j++)
{
if(G.AdjMatrix[i][j]==MaxInt)
printf("\t∞");minimal
else printf("\t%d",G.AdjMatrix[i][j]);
}
printf("\n");
}
}
int minimal(MGraph *G,ShortEdge *shortedge)
{
int i,j;
int min,loc;
min=MaxInt;
for(i=1;i<G->vexnum;i++)
{
if(min>shortedge[i].lowcost&&shortedge[i].lowcost!=0)
{
min=shortedge[i].lowcost;
loc=i;
}
}
return loc;
}
void MiniSpanTree_Prim(MGraph *G,VertexType start)
{
int i,j,k;
ShortEdge shortedge[VertexMax];
/
/1.处理起始点start
k=LocateVex(G,start);
for(i=0;i<G->vexnum;i++)
{
shortedge[i].adjvex=start;
shortedge[i].lowcost=G->AdjMatrix[k][i];
}
shortedge[k].lowcost=0;//lowcost为0表⽰该顶点属于U集合
//2.处理后续结点
for(i=0;i<G->vexnum-1;i++)//对集合U，去最短路径的顶点
{
k=minimal(G,shortedge);//最短路径的顶点
printf("%c->%c,%d\n",shortedge[k].adjvex,G->Vertex[k],shortedge[k].lowcost);//输出到的最短路径顶，及路径权值
shortedge[k].lowcost=0;//将到的最短路径顶点加⼊集合U中
for(j=0;j<G->vexnum;j++)//U中加⼊了新节点，可能出现新的最短路径，故更新shortedge数组
{
if(G->AdjMatrix[k][j]<shortedge[j].lowcost)//有更短路径出现时，将其替换进shortedge数组
{
shortedge[j].lowcost=G->AdjMatrix[k][j];
shortedge[j].adjvex=G->Vertex[k];
}
}
}
}
int main()
{
VertexType start;
MGraph G;
CreateUDN(&G);
print(G);
printf("请输⼊起始点：");
scanf(" %c",&start);//%c前⾯有空格
MiniSpanTree_Prim(&G,start);
return0;
}
执⾏结果
普⾥姆算法时间复杂度分析：
2
在MiniSpanTree_Prim函数中，主要是后部分的⼆重循环故时间复杂度为O（n），其中n为顶点数，故Prim的时间复杂度与顶点数有关。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。