最小生成树的应用数据结构课程设计

开 始 功能选择 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