第1步：在V中任取一顶点v，V1?{v}，V2?V?V1，E1??，循环变量赋值k?0；

第2步：对于所有连接V1和V2的边eij?[vi,vj]，其中vi?V1，vj?V2，如果不存在连接V1和V2的边eij?[vi,vj]，算法终止，无支撑树，否则继续第3步；

第3步：取满足w[u,v]?minw(eij)的边[u,v]，其中u?V1，v?V2，令

vi?V1vj?V2V1?V1?{v}，V2?V2?{v}，E1?E1?{[u,v]}，k?k?1；

第4步：如果V2??，或者k?n?1，得最小支撑树T?(V,E1,w)，算法终止，否则转第2步。

例9-2 用Prim算法构造图9-1的最小支撑树。

解：根据Prim算法，不断选择权最小的边，新增边必须与已选边连通且不构成回路，所选边顺序：[v2,v7]，[v7,v8]，[v1,v2]，[v2,v3]，[v3,v4]，[v4,v5]，

[v5,v6]。具体步骤见图9-3(a)~(g)。

v8v1513 134181v5vv8v1513 134181v5v11 12 10 14138 143211 12 10 14138 1432vvvvv717v6v5vv717v6

(a) (b)

v8v1513 134181v8v1513 134181v5v11 12 10 14138 143211 12 10 14138 1432vvvvv717v6v717v6

(c) (d)

9

v8v1513 134181v5vv8v1513 134181v5v11 12 10 14138 143211 12 10 14138 1432vvvvv717v6v8vv717v6

(e) (f)

1513 13418111 12 10 14138 1432v5vvvv717v6

(g)

图9-3

3、破圈法

破圈法和Kruskal算法的方向相反，逐步将网络中权最大的边去除，直至网络形成支撑树。破圈法也称为破回路法。具体算法请读者仿照Kruskal算法或Prim算法建立。

例9-3 用破圈法构造图9-1的最小支撑树。

解：根据破圈法，不断将权最大的边剔除，每步剔除边时必须保证图的连通性，每步剔除的边分别为：[v1,v4]，[v6,v7]，[v5,v8]，[v5,v6]，[v1,v8]。具体步骤见图9-4(a)~(e)。

v8v1513 1341v5vv8v1513 1341v5v11 12 10 14138 143211 12 10 14138 1432vvvvv717v6

v7v6

(a) (b)

10

v813 1341v5vvv813 134111 12 10138 1432v5vv11 12 10 14138 1432vvvvv7v6

v7v5v6

(c) (d)

v8v1v41311 12 10138 1432vvv7(e)

图9-4

v6

题型II 求网络的最短路问题

1、Dijkstra算法

Dijkstra算法是当前公认的求无负赋权有向图最短路径的最好算法，Dijkstra算法采用标号的方法，可求从顶点v1至其余顶点的最短路径。Dijkstra算法步骤如下：

第1步：k?1,取L1(v1)?0；L1(vj)???(j?2,3,?,n)

取L1(v*)?minL1(vj)，A?{v1},A?V?A，

vj?Vd(v1,v1)?0；

第2步：对于vj?A，k?k?1，

令Lk(vj)?min{Lk?1(vj),Lk?1(v*)?w(v*,vj)}， 取Lk(v*)??minL2(vj)，A?A?{v*}，A?A?{v*}，

vj?Ak?k?1，d(v1,v*)?Lk(v*)；

第3步：若d(v1,v*)???，D中v1至A的路径不存在，算法终止，否则继续第4步；

11

第4步：若k?n，则输出最短路径的长度Ln(v1,v*)，算法终止，否则转第2步。

上述Dijkstra算法可以给出最短路径长度是否存在及其长度，如果还要给出具体的最短路径，则要将每一步Lk(v*)中的v*记录下来，同时记录其前列顶点。

在比较简单的赋权有向图的实际计算中，常采用一种表格形式的Dijkstra算法。

例9-4 用Dijkstra算法求图9-5所示网络中从顶点v1到其余顶点的最短路。

v23v572 4 5v125 1 8v462v7v33v6

图9-5

解：采用表格形式的Dijkstra算法，步骤如下：

vj k?1 v1v2??v?Vv3??v4v5v6v7 L1(vj) 0*???????? v*?v1，d(v1,v1)?L1(v*)?minL1(vj)?0，A?{v1}；

vj k?2 v1v22*v?Vv35v4v5v6v7 L2(vj) 0*???????? v*?v2，d(v1,v2)?L2(v*)?minL2(vj)?2，A?{v1,v2}，前列顶点v1；

vj k?3 v1v22*v?Vv34*v46v55v6v7 L3(vj) 0*???? v*?v3，d(v1,v3)?L3(v*)?minL3(vj)?4，A?{v1,v2,v3}，前列顶点v2；

vj k?4 v1v22*v34*v45*v55v6v7 L4(vj) 0*???? 12