首页 > 代码库 > Prim算法（普里姆算法）
Prim算法（普里姆算法）
描述：
一个连通图的生成树是指一个极小连通子图，它含有图中的全部顶点，但只有足以构成一棵树的 n-1 条边。我们把构造连通网的最小代价生成树成为最小生成树。而Prim算法就是构造最小生成树的一种算法。
定义：
假设N = （P，{E}）是连通网，TE是N上最小生成树中边的集合。算法从U = {U0}（U0属于V）。开始重复执行下述操作：在所有u属于U，v属于V-U的边（u,v）属于E中找到一条代价最小的边（u0，v0）并入集合TE，同事v0并入U，知道U = V为止。此时TE中必有n-1条边，则T = （V，{TE}）为N的最小生成树
功能：
假设你是电信的实施工程师，需要为一个镇的九个村庄架设通信网络做设计，村庄零星地分布在这个镇中，每个村庄之间都有一定的距离，我们可以用prim算法找到一种连接方式。用这种方式可以保证总的路径最短。
代码：
#include <stdio.h>#include <stdlib.h>#define MAXVERTEX 10#define INF 65535typedef char VertexType;typedef int EdgeType;typedef struct MGraph{ VertexType data[MAXVERTEX]; EdgeType edge[MAXVERTEX][MAXVERTEX]; int numVertex; int numEdge;}MGraph;//构造一个图void CreateMGraph(MGraph *G){ int i = 0,j = 0,k = 0,w = 0; VertexType c; printf("请输入顶点的数目和边的数目：中间用逗号隔开，回车表示结束:\n"); scanf("%d,%d",&G->numVertex,&G->numEdge); fflush(stdin); printf("请输入顶点存储的数据,以回车表示结束:\n"); scanf("%c",&c); while(i < G->numVertex) { if(c == ‘\n‘) break; G->data[i] = c; i++; scanf("%c",&c); } for(i = 0;i < G->numVertex;i++) { for(j = 0;j < G->numVertex;j++) { if(i == j) G->edge[i][j] = 0; else G->edge[i][j] = INF; } } fflush(stdin); for(k = 0;k < G->numEdge;k++) { printf("请输入边vi-vj依附顶点的下标 i 和 j ，以及权值w，中间用逗号隔开，回车表示结束:\n"); scanf("%d,%d,%d",&i,&j,&w); G->edge[i][j] = w; G->edge[j][i] = G->edge[i][j]; } printf("\n得到的邻接矩阵为：\n"); for(i = 0;i < G->numVertex;i++) { for(j = 0;j < G->numVertex;j++) { printf("%d ",G->edge[i][j]); } printf("\n"); }}void Prim(MGraph *G){ int i = 0,j = 0,k = 0,min,m; int adjvex[MAXVERTEX]; int lowcost[MAXVERTEX]; for(i = 0;i < G->numVertex;i++) { adjvex[i] = 0; } lowcost[0] = 0; for(i = 1;i < G->numVertex;i++) { lowcost[i] = G->edge[0][i]; } for(i = 1;i < G->numVertex;i++) { j = 1,k = 0; min = INF; while(j < G->numVertex) { if(lowcost[j] != 0 && lowcost[j] < min) { min = lowcost[j]; k = j; } j++; } printf("(%d,%d) ",adjvex[k],k); lowcost[k] = 0; for(j = 1;j < G->numVertex;j++) { if(lowcost[j] != 0 && G->edge[k][j] < lowcost[j]) { lowcost[j] = G->edge[k][j]; adjvex[j] = k; } } }}int main(){ MGraph G; CreateMGraph(&G); printf("\n******************************\n"); printf("\n运用Prim算法得到的最短路径为：\n"); Prim(&G); printf("\n******************************\n"); return 0;}
Prim算法（普里姆算法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。