初始无向图
Prim算法思想：
将图中的节点分为两部分，一部分在集合U中（已添加到生成树中的节点的集合），另一部分在集合V-U中，V代表图中的全部节点
对于每一个节点，对应一个closedge数组中的元素，拥有两个域：adjvex：与其相邻的节点v，它总是U中的节点
lowcost：与节点v的权值
从任意一个节点n开始，将n并入集合U，n的lowcost置为0，初始化closedge数组中n之外的所有元素的adjvex和lowcost，
然后进行n-1次循环，n为节点总数
从closedge数组中找出lowcost最小的元素，将其索引值的lowcost置为0，相当于加入集合U，输出找出的边的信息，之后对closedge数组进行更新，
解释一下为什么要进行更新：
U中的节点增加了，出现了之前没有的节点，那么V-U中的节点vex与新增节点的权值newcost就需要与closedge[vex]的lowcost值进行比较，如果newcost更小，就需要把vex的adjvex更新为新增节点，lowcost更新为newcost
代码：
/*************************** * Prim算法--最小生成树 * ***************************/ //注意：<span style="color:#330033;background-color:rgb(255,255,0);">实际节点是从1开始，代码实现的时候是从零开始</span> /*************************** 测试数据： 6 10 1 2 6 1 3 1 1 4 5 2 3 5 2 5 3 3 4 5 3 5 6 3 6 4 4 6 2 5 6 6 1 ***************************/ #include<stdio.h> #include<stdlib.h> #include<iostream> #include<algorithm> #include<math.h> #include<string.h> using namespace std; #define min(x,y) (x)<(y)?(x):(y) #define maxn 65535 typedef struct { int adjvex; //与本节点相邻的节点 int lowcost; //与adjvex的权值 } T; T closedge[100]; int adj[100][100]; int n; void createAdj() { int arc; printf("请输入节点和边的个数："); cin>>n>>arc; //初始化邻接矩阵 for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(i == j) adj[i][j] = 0; else adj[i][j] = maxn; printf("请输入图中的边，按照首节点、尾节点、权值的格式：\n"); int a, b, w; for(int i = 0; i < arc; i++) { cin>>a>>b>>w; adj[a-1][b-1] = w; adj[b-1][a-1] = w; } } void prime(int k) { printf("+++++++++++++++++++\n"); k -= 1; for(int i = 0; i < n; i++) if(i != k) { closedge[i].adjvex = k; closedge[i].lowcost = adj[k][i]; } closedge[k].lowcost = 0; int mark = k; for(int i = 0; i < n; i++) { if(i == mark) continue; int tmp; //寻找出与k相邻的最小节点，并存入tmp中 int minx = maxn; for(int j = 0; j < n; j++) { if(closedge[j].lowcost && minx > closedge[j].lowcost) { minx = closedge[j].lowcost; tmp = j; } } printf("%d -- >%d, 权值为%d\n", closedge[tmp].adjvex+1, tmp+1, closedge[tmp].lowcost); k = tmp; closedge[k].lowcost = 0; //更新权值，因为生成树中的节点多了一个，closedge数组的lowcost域需要进行更新 for(int j = 0; j < n; j++) { if(adj[k][j] < closedge[j].lowcost) { closedge[j].adjvex = k; closedge[j].lowcost = adj[k][j]; } } } printf("+++++++++++++++++++\n"); } int main() { memset(adj, 0, sizeof(adj)); createAdj(); int b; printf("请输入您要从哪个节点开始构建最小生成树："); cin>>b; prime(b); return 0; }程序运行结果：
