普利姆算法实现 C语言版 + C++版 +例题“村村通工程”

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。

时间复杂度

编辑播报

这里记顶点数v，边数e

邻接矩阵:O(v2) 邻接表:O(elog2v)[1]

C++：

#include <iostream>using namespace std;//#define max 100#define maxInt 32767//图的表示typedef struct{//用来放顶点名称的字符数组char vexs[100];//定义一个方阵用来存放权值的值int arcs[100][100];//定义顶点的个数和权值的个数int vexnum, arcnum;} AMGraph;//到 该顶点 的 最小权值边 的集合（不断更新）struct{char adjvex; //所到的顶点int lowcost; //权值} closeedge[100]; //最小权值的数组//找到 当前出发顶点 的 位置int LocateVex(AMGraph G, char v){//遍历 图的名称数组vexs，找到其位置for(int i = 0; i < G.vexnum; i++){if(G.vexs[i] == v)return i;}//未找到返回-1return -1;}//创建无向图void CreateUDN(AMGraph &G){int i, j, k;//先输入 顶点个数 和 边个数cout << "请输入顶点个数和边的个数"<<endl;cin >> G.vexnum >> G.arcnum;cout << endl;//然后输入所有 顶点的名字cout << "请输入所有顶点的名字:" << endl;for(i = 0; i < G.vexnum; i++){cout << "请输入第 " << (i+1) << "个顶点的名字" << endl;cin >> G.vexs[i];}cout << endl;//对权值矩阵（邻接矩阵）初始化for(i = 0; i < G.vexnum; i++){for(j = 0; j < G.vexnum; j++){//全初始化 为最大值G.arcs[i][j] = maxInt;}}//输入 两个顶点 以及 边的权值cout << "输入权值和顶点如：a b 12" << endl;for(k = 0; k < G.arcnum; k++){int weight; //用来临时 存放权值char v1, v2; //用来临时 存放两条边//输入 权值 和 两条边cout << "请输入权值和两个顶点" << (k+1) << "arc " <<endl;cin >> v1 >> v2 >> weight;//通过 两个顶点 在 名称数组中的位置 找到 这条边权值在矩阵中的位置i = LocateVex(G,v1);j = LocateVex(G,v2);//把这条边的 权值 放到 邻接矩阵中G.arcs[i][j] = G.arcs[j][i] = weight;}}//更新存放 到达目标顶点所需最小权值边 的数组，用来进行贪心选择int Min(AMGraph G){int i;int index = -1;int min = maxInt;for(i = 0; i < G.vexnum; i++){//选出当前最小的权值， 并且没有被选中过if(min > closeedge[i].lowcost && closeedge[i].lowcost != 0){//最小值min = closeedge[i].lowcost;index = i;}}return index;}//最小生成树算法,u表示起始的顶点void prim(AMGraph G, char u){int k, j, i;char u0, v0;//找到起始顶点的位置k = LocateVex(G, u);//找到 该顶点 与 其他顶点连成的边的权值，放入 最小权值数组 中for(j = 0; j < G.vexnum; j++){//除了自己if(j != k){//把指向的顶点名放入顶点名数组中closeedge[j].adjvex = u;//把指向顶点边的权值放入最小权值数组中closeedge[j].lowcost = G.arcs[k][j];}}closeedge[k].lowcost = 0;for(i = 1; i < G.vexnum; i++){//找到新的最小权值边的位置k = Min(G);u0 = closeedge[k].adjvex;v0 = G.vexs[k];cout << u0 << "-->" << v0 << endl;//选择过的权值边标记为0closeedge[k].lowcost = 0;for(j = 0; j < G.vexnum; j++){//如果新的边权值更小，那就替换掉原来的边if(G.arcs[k][j] < closeedge[j].lowcost){closeedge[j].adjvex = G.vexs[k];closeedge[j].lowcost = G.arcs[k][j];}}}}int main(){AMGraph G;CreateUDN(G);cout << endl;prim(G, 'a');cout << endl;return 0;}

c：

#include <stdio.h>#include <stdlib.h>typedef char VerTexType; //假设顶点的数据类型为字符型typedef int ArcType;//假设边的权值类型为整型#define MVNum 100 //最大顶点数#define MaxInt 32767//最大值//辅助数组的定义，用来记录从顶点集到V-U的权值最小的边struct{VerTexType adjvex; //最小边在U中的那个顶点ArcType lowcost;//最小边上的权值} closedge[MVNum];//图的邻接表存储表示typedef struct{VerTexType vexs[MVNum]; //顶点表ArcType arcs[MVNum][MVNum];//邻接矩阵int vexnum, arcnum; //图的当前点数和边数}AMGraph;//找到当前出发点的位置int LocateVex(AMGraph* G, VerTexType v){//确定点v在G中的位置for(int i = 0; i < G->vexnum; i++){if(G->vexs[i] == v){return i;}}return -1;}void CreateUDN(AMGraph* G){//采用邻接矩阵表示法，创建无向网Gint i, j, k;printf("请输入总顶点数、总边数、以空格隔开：");scanf("%d %d",&G->vexnum, &G->arcnum);getchar();printf("\n");printf("输入点的名称，如a b 10:\n");for(i = 0; i < G->vexnum; i++){printf("请输入第%d个点的名称：",i+1);scanf("%c",&G->vexs[i]);//printf("%c", G->vexs[i]);//测试用getchar();}//初始化领接矩阵，边的权值均置为极大值MaxIntfor(i = 0; i < G->arcnum; i++){for(j = 0; j < G->arcnum; j++){G->arcs[i][j] = MaxInt;}}printf("输入两个顶点和对应的权值，如a b 5：\n");for(k = 0; k < G->arcnum; k++){VerTexType v1, v2;ArcType w;printf("输入第%d条边依附的顶点及权值:",k+1);scanf("%c %c %d", &v1, &v2, &w);getchar();//找到两条边确定的邻接矩阵的位置i = LocateVex(G, v1);j = LocateVex(G, v2);G->arcs[i][j] = w;//邻接矩阵是对称的G->arcs[j][i] = G->arcs[i][j];}}int Min(AMGraph G){//返回权值最小的点int i;int index = -1;int min = MaxInt;for(i = 0; i < G.vexnum; i++){if(min > closedge[i].lowcost && closedge[i].lowcost != 0){min = closedge[i].lowcost;index = i;}}return index;}//普利姆算法void MiniSpanTree_Prim(AMGraph G, VerTexType u){int k, j, i,w0;VerTexType u0, v0;k = LocateVex(&G, u);for(j = 0; j < G.vexnum; j++){if(j != k){closedge[j].adjvex = u;closedge[j].lowcost = G.arcs[k][j];}}closedge[k].lowcost = 0;for(i = 1; i < G.vexnum; i++){k = Min(G);u0 = closedge[k].adjvex;v0 = G.vexs[k];w0 = closedge[k].lowcost;printf("边：%c-->%c %d\n",u0,v0,w0);closedge[k].lowcost = 0;for(j = 0; j < G.vexnum; j++){if(G.arcs[k][j] < closedge[j].lowcost){closedge[j].adjvex = G.vexs[k];closedge[j].lowcost = G.arcs[k][j];}}}}int main(){AMGraph G;CreateUDN(&G);printf("\n创建无向图G完成！\n");printf("利用普利姆算法构造最小生成树结果：\n");//输入图和起始顶点MiniSpanTree_Prim(G, '1');printf("\n");return 0;}

7-1 最小生成树构造

某地对偏远地区实行“村村通”工程，目标是使整个地区任何两个村落间都可以实现快速交通（但不一定有直接的快速道路相连，只要互相间接通过快速路可达即可）。现得到拟修建道路的费用，现请你编写程序，计算出全地区畅通需要的最低成本。

输入格式:

输入的第一行给出村庄数目N (1≤N≤20)和拟修建的道路数M

接下来的M行对应修建每条村庄间道路的成本，每行给出3个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本。

输出格式:

输出需修建的道路，按prim算法从编号1开始得到的顺序，输出每条路，每行输出一条道路，形式如：道路1编号,道路2编号,费用。(编号小的放前面，编号大的放后面，逗号为英文状态下的逗号)

输入样例:

4 61 2 11 3 41 4 12 3 32 4 23 4 5

输出样例:

1,2,11,4,12,3,3

#include <stdio.h>#include <stdlib.h>typedef int VerTexType; //假设顶点的数据类型为字符型typedef int ArcType;//假设边的权值类型为整型#define MVNum 100#define MaxInt 32767//辅助数组的定义，用来记录从顶点集到V-U的权值最小的边struct{VerTexType adjvex; //最小边在U中的那个顶点ArcType lowcost;//最小边上的权值} closedge[MVNum];//图的邻接表存储表示typedef struct{VerTexType vexs[MVNum]; //顶点表ArcType arcs[MVNum][MVNum];//邻接矩阵int vexnum, arcnum; //图的当前点数和边数}AMGraph;int LocateVex(AMGraph* G, VerTexType v){//确定点v在G中的位置for(int i = 0; i < G->vexnum; i++){if(G->vexs[i] == v){return i;}}return -1;}void CreateUDN(AMGraph* G){//采用邻接矩阵表示法，创建无向网Gint i, j, k;//printf("请输入总顶点数、总边数、以空格隔开：");scanf("%d %d",&G->vexnum, &G->arcnum);//getchar();//printf("\n");//printf("输入点的名称，如a:\n");for(i = 0; i < G->vexnum; i++){//printf("请输入第%d个点的名称：\n",i+1);G->vexs[i] = i+1;//printf("%d", G->vexs[i]);//测试用//getchar();}//初始化领接矩阵，边的权值均置为极大值MaxIntfor(i = 0; i < G->arcnum; i++){for(j = 0; j < G->arcnum; j++){G->arcs[i][j] = MaxInt;}}//printf("输入边依附的顶点的权值，如a b 5：\n");for(k = 0; k < G->arcnum; k++){VerTexType v1, v2;ArcType w;//printf("输入第%d条边依附的顶点及权值:",k+1);scanf("%d %d %d", &v1, &v2, &w);//printf("%c %c %d", v1, v2, w);getchar();i = LocateVex(G, v1);j = LocateVex(G, v2);G->arcs[i][j] = w;G->arcs[j][i] = G->arcs[i][j];}}int Min(AMGraph G){//返回权值最小的点int i;int index = -1;int min = MaxInt;for(i = 0; i < G.vexnum; i++){if(min > closedge[i].lowcost && closedge[i].lowcost != 0){min = closedge[i].lowcost;index = i;}}return index;}void MiniSpanTree_Prim(AMGraph G, VerTexType u){int k, j, i,w0;VerTexType u0, v0;k = LocateVex(&G, u);for(j = 0; j < G.vexnum; j++){if(j != k){closedge[j].adjvex = u;closedge[j].lowcost = G.arcs[k][j];}}closedge[k].lowcost = 0;//printf("\n");for(i = 1; i < G.vexnum; i++){k = Min(G);u0 = closedge[k].adjvex;v0 = G.vexs[k];w0 = closedge[k].lowcost;if(u0 > v0){int m = u0;u0 = v0;v0 = m;}printf("%d,%d,%d\n",u0,v0,w0);closedge[k].lowcost = 0;for(j = 0; j < G.vexnum; j++){if(G.arcs[k][j] < closedge[j].lowcost){closedge[j].adjvex = G.vexs[k];closedge[j].lowcost = G.arcs[k][j];}}}}int main(){AMGraph G;CreateUDN(&G);//printf("\n创建无向图G完成！\n");//printf("利用普利姆算法构造最小生成树结果：\n");MiniSpanTree_Prim(G, 1);return 0;}