网图的最小生成树prim（普利姆）算法

算法"/>

网图的最小生成树prim（普利姆）算法

#include<stdio.h>
#include<limits.h>
#define INF 0x3f3f3f3f
//定义辅助表类型
struct Nodetype {int adjvex;int lowcost;
};
//定义图结构，包括邻接矩阵和顶点信息数组，边和顶点数量
struct Graph {int matrix[100][100];char vertex[100];int vernum, edgenum;
};
//初始化图
void Creategraph(Graph &g,char a[],int edgenumber,int vernumber)
{g.vernum = vernumber;g.edgenum = edgenumber;for (int i = 0; i < g.vernum; i++)g.vertex[i] = a[i];for (int i = 0; i < g.vernum; i++)for (int j = 0; j < g.vernum; j++){if (i == j)g.matrix[i][j] = 0;elseg.matrix[i][j] = INF;}int v1, v2, weight;for (int i = 0; i < g.edgenum; i++){printf("请输一条边的两个顶点序号和权值：\n");scanf_s("%d,%d,%d", &v1, &v2, &weight);g.matrix[v1][v2] = weight;g.matrix[v2][v1] = weight;}}
//寻找最短邻接边，即找出辅助表中lowcost域最小的值对应的数组下标并返回
int  Minedge(Nodetype a[], int n)
{int min= INF;int temp;for (int i = 0; i < n; i++){if (a[i].lowcost < min&&a[i].lowcost != 0){min = a[i].lowcost;temp = i;}}return temp;}
//普利姆算法
void prim(Graph g,int start)
{//初始化辅助表Nodetype shortedge[100];for (int i = 0; i < g.vernum; i++){shortedge[i].adjvex = start;shortedge[i].lowcost = g.matrix[start][i];}//起点元素先进集合ushortedge[start].lowcost = 0;for (int i = 0; i < g.vernum - 1; i++){int k = Minedge(shortedge, g.vernum);//寻找u这个整体所对应的最小边printf("(%d,%d)%d\n", k, shortedge[k].adjvex, shortedge[k].lowcost);//输出对应边//加入了k这个结点构成了新的整体//这时候要对比一下原来的整体跟k这个结点关于余下的v-u这些顶点的边的大小关系//若k到v-u的某一顶点的边的权值要比原来的整体要小，则要更新for (int j = 0; j < g.vernum; j++){if (g.matrix[k][j] < shortedge[j].lowcost){shortedge[j].adjvex = k;shortedge[j].lowcost = g.matrix[k][j];}}}
}int main()
{char a[] = "ABCDEF";Graph g;Creategraph(g, a, 9, 6);//测试邻接矩阵/*for (int i = 0; i < g.vernum; i++){for (int j = 0; j < g.vernum; j++)printf("%d                ", g.matrix[i][j]);printf("\n");}*/prim(g, 3);
}