图的连通性之普里姆算法和克鲁斯卡尔算法

问题：

假设要在 n 个城市之间架设通信网络， 对一个无向图，从理论上讲最多有 n(n-1)12 条线路供选择，但实际上仅需要其中的 N-1 条就够了。当然，每条线路都要付出代价。 那么，如何得到总代价最少的 N-1 条线路呢?

普里姆算法

假设 N=(V，{E})是是连通网，TE 是 N 上最小生成树中边的集合。算法从 U={uo}( uo∈V)，TE={}开始，重

复执行下述操作:在所有的边(u,v) (v EV-U)中选择代价最小的一条边(u0,v0)并入集合 TE，同时将 v0 并入 U,直到 U=V 为止。此时 TE 集合中的边为最小代价生成树。

上图的最小代价生成树：

• 算法

Void MinSpanTree-PRIM(MgraphGVertexType u){

//struct {// (closedge 包括两部分:邻接顶点和边的代价)

VertexType adjvex;

VRType lowcost;(边的代价)

//}closedge[MAX-VERTEX-NUM];

k= locateVex(G,u);(k 是图中任一出发顶点 u 的下标)

for( j=0;j<G.vexnum; ++j)

(辅助数组 closedge 初始化，即邻接矩阵初始化)

if ( j! = k) closedge[j] = {u,G.arcs[k] [j].adj };

(u 为顶点，G.arcs[i].adj 为代价)

Closedge[k].lowcost=0;(初始，U= {u})

for( i=1; i<G.vexnum; ++i){(选择其余 G.vexnum-1 个顶点)

k=minmum(closedge);(求出 T 的下一个结点;第 k 个顶点)

(此时 closedge[k].lowcost=MIN{closedge[vi].lowcost closedge[vi]lowcost>0} )

(加上大于 0 的比较，就是避免在正整数中 0 最小的情况)

printf(closedge[k].adjvex,G.vexs[k]);(输出生成树的边)

closedge[k].lowcost=0;(第 K 个顶点并入 U 集合，将代价置 0)

for ( j = 0;j<G.vexnum;++j)

if (G.arcs[k] [i].adj<closedge[i.lowcost)

(新顶点并入 U 后重新选择最小边)

closedge[i] ={G.vexs[k],G.arcs[k] [j].adj};

(用代价小的边带替大代价的边)

}

}//MinSpanTree-PRIM

克鲁斯卡尔算法

假设连通网 N =(V，{E}),则令最小生成树的初始状态为只有 N 个顶点而无边的非连通图 T=(V，{})，图中每个顶点自成一个连通分量。在 E 中选择代价最小的边，若该边依附的顶点落在 T 中不同的连通分量上，则将此边加入到 T 中，否则舍去此边而选择下一条代价最小的边。依次类推，直至 T 中所有顶点都在同一连通分量上为止。

用克鲁斯卡尔算法画出最小生成树

个人感觉这个好用😀