发布时间 : 星期一 文章最小生成树的应用数据结构课程设计更新完毕开始阅读
开 始 功能选择 1、建立邻接矩阵 2、用prim算法求解3、用kruskal算法最最结 束 图4.1 流程图
(2)最小生成树Prim算法及代价模块代码
int prim(int g[][max],int n) {
int lowcost[max],prevex[max]; int i,j,k,min;int sum=o; for(i=2;i<=n;i++) { lowcost[i]=g[1][i]; prevex[i]=1; } lowcost[1]=0; for(i=2;i<=n;i++) //形成n-1条边的生成树 { min=inf;
k=0;
for(j=2;j<=n;j++)
if((lowcost[j] 7 k=j; } printf(\ sum+=min; lowcost[k]=0; for(j=2;j<=n;j++) if(g[k][j] cout<<\最少生成树的代价:\ cout< 8 return 0;} 开 始 输入ch, 用于判断是 否创建无向网 ch==’Y’ 否 是 1. 调用create()函数 否 flag==0 是 2.调用display()函数 输入起点st 是 st==0 否 3.调用prim ()函数 4.调用Minium ()函数 结 束 图4.2 Prim算法流程图 9 (3) 最小生成树kruskal算法及代价模块代码 void MiniSpanTree(MGraphA *D)//生成最小生成树 { int i, j, n, m, SUM=0; int k = 1; int parent[M]; edge edges[M]; for ( i = 1; i < D->vexnum; i++) { for (j = i + 1; j <= D->vexnum; j++){ if (D->arc[i][j].adj == 1) { edges[k].begin = i; edges[k].end = j; edges[k].weight = D->arc[i][j].weight; k++;} } } sort(edges, D); for (i = 1; i <= D->arcnum; i++) { parent[i] = 0; } printf(\最小生成树为:\\n\ for (i = 1; i <= D->arcnum; i++)//核心部分 { n = Find(parent, edges[i].begin); m = Find(parent, edges[i].end); if (n != m){ parent[n] = m; 10