数据结构，最小生成树克鲁斯卡尔算法的实现

k=j; } }

if (t[e[k].vexh].jihe!=t[e[k].vext].jihe) {

e[k].flag=1;

for (j=1;j<=G->n;j++)

if (t[j].jihe==t[e[k].vext].jihe) t[j].jihe=t[e[k].vexh].jihe; t[e[k].vext].jihe=t[e[k].vexh].jihe; i++;

} else e[k].flag=2; }

printf(\克鲁斯卡尔最小生成树：\\n\ for (i=0;ie;i++) if (e[i].flag==1)

printf(\%d\\n\输出最小生成树 }

该步骤应用的是克鲁斯卡尔算法，它的基本思想是：每次选不属于同一连通分量(保证不生成圈)且边权值最小的顶点，将边加入MST（Minimum Spanning Tree最小生成树），并将所在的2个连通分量合并，直到只剩一个连通分量。

7

流程如图4.2所示。

8

开始请输入该图的顶点数和边数G.e>(G.n-1)*G.n/2输入错误,请重新输入请输入该图的顶点信息i=1i<=G.ni++getchar();scanf(\(G.vexs[i]))i=1i++i<=G.nj=1j<=G.nj++ G.edges[i][j].w=0请输入该图每条边对应的两个顶点的名称K=1k<=G.e请输入第%d条边的顶点序号请输入第%d条边的权值K++大小i=1ch1!=G.vexs[i]j=1i++ch2!=G.vexs[j]return Gj++e[p].vexh=i;e[p].vext=j; e[p].weight=G.edges[i][j].w=ch3; //权值 e[p].flag=0;p++;结束图4.1

9

开始i=1i++i<=G->nt[i].data=G->vexs[i];t[i].jihe=i;i=1inmin=MaxVertexNum;j=0j++jee[j].weightnt[j].jihe==t[e[k].vext].jihet[j].jihe=t[e[k].vexh].jihe; t[e[k].vext].jihe=t[e[k].vexh].jihe; i++;i=0i++iee[i].flag==1输出最小生成树结束图4.2

10