图论算法.doc

图论算法

§1 最小生成树

1．1 生成树的概念

 设图 G＝(V，E)是一个连通图，当从图中任一顶点出发遍历图 G 时，将边集 E(G)分成两个集合 A(G)和

B(G)。其中 A(G)是遍历图时所经过的边的集合，B(G)是遍历图时未经过的边的集合。显然，G1＝(V，A)

是图 G 的子图，则称子图 G1 是连通图 G 的生成树。图的生成树不是惟一的。如对图 1(a)，当按深度和广

度优先搜索法进行遍历就可以得到图 1 中(b)和(c)的两棵不同的生成树，并分别称之为深度优先生成树和

广度优先生成树。

线路中选择 n-1 条使该网络的建造费用最少，这就是下面要讨论的最小生成树问题。

1.2 网的最小生成树

 在前面我们已经给出图的生成树的概念。这里来讨论生成树的应用。

 假设，要在 n 个居民点之间敷设煤气管道。由于，在每一个居民点与其余 n－1 个居民点之间都可能敷

设煤气管道。因此，在 n 个居民点之间，最多可能敷设 n(n-1)/2 条煤气管道。然而，连通 n 个居民点之间

的管道网络，最少需要 n-1 条管道。也就是说，只需要 n-1 条管道线路就可以把 n 个居民点间的煤气管道

连通。另外，还需进一步考虑敷设每一条管道要付出的经济代价。这就提出了一个优选问题。即如何在

n(n-1)/2 条可能的线路中优选 n-1 条线路，构成一个煤气管道网络，从而既能连通 n 个居民点，又能使总

的花费代价最小。

 解决上述问题的数学模型就是求图中网的最小生成树问题。把居民点看作图的顶点，把居民点之间的煤

不再考虑。

 (3)如此依次进行，直到选够(n-1)条边即得到最小生成树。



 现以图 2 为例说明此算法。设此图是用边集数组 EV 表示的，且数组中各边是按权值由小到大的次序排

列，如下表所示。

k 1 2 3 4 5 6 7 8 9 10

EV[k].p1 2 2 4 2 6 5 1 1 1 5

EV[k].p2 3 4 3 6 4 7 5 6 2 6

COST[EV[k].p1,EV[k].p2] 5 6 10 11 14 18 19 21 27 33

 按权值由小到大选取各边就是在数组中按下标 k 由 1 到 en(图中边数)的次序选取。选前 2 条边(2，3)，

 这可用将各顶点划分为集合的办法解决：假设数组 tag(1..en)作为顶点集合划分的标志初值为 0。在算

法的执行过程中，当所选顶点 u，v 是连通的，则将相应位置的 tag[u]，tag[v]置以相同的数字，而不连通

的点在初期分属不同的集合，置不同的数字；一旦两个不同的连通分支连通了，则修改 tag 的值，将新的

连通分支改为相同的数字。我们以图 2 为例。首先选(2，3)(2，4)边，由于是连通的，并且不出现回路。

tag[2]:＝1，tag[3]:=tag[4]:=1 是同一个集合 A；选(6，2)边与 A 集合连通；tag[6]:=1；再选(5，7)与集合

A 不连通，tag[5]:＝ tag[7]:＝2 构成另一集合 B；选(1，5)边与集合 B 连通，tag [1]:=2；此时，集合 A＝

{2，3，4，6}；集合 B＝{5，7，1}；当选(1，6)边时，(1，6)与集合 A、集合 B 都连通，并且两个顶点分

别属于两个不同的集合 A、B，这使得集合 A 与集合 B 通过边(1，6)连通。修改集合 B 中 tag 的值，置为

1，即将集合 B 并入集合 A。边为 n-1 条，这就是一棵最小生成树。

 根据集合标志数组 tag 的变化过程，很容易判断，选择一条新的边是否构成回路。当新选边的两个顶点

对，即 EV[K].P1 存放一个顶点，边的另一顶点存放在 EV[K].P2 之中。

 tag(1..n)：顶点集合划分标志的数组。

 Enumb：当前生成树的边数。

 SM：当前权累计和。

；；

；





 ：＝!；"#$%!&诸参量初始化'

($%)&边数累计'

7，； $% 8)； &最小生成树增加一条边'

"#$%"#8"0，1；

#，*；&选 ， 不会形成环，合并 ，* 集合，并修改 '

9

:$%:8)&找下一条边'

9

4 ,-)+7;<;

"7"#

.；

由算法可知图 2 的最小生成树的结果是(2，3)，(2，4)，(2，6)，(5，7)，(1，5)，(1，6)。

从城市 v 到城市 W 的航线，弧 V—>w 上的标号代表从 V 城飞到 w 城所需要的时间。要寻找由该航空图上

一给定城市到另一城市所需要的最短飞行时间。可以用求解这个有向图的单源最短路径算法来完成。

前的最短距离，其初值为 dist[i]:=cost[v0，i]，(i=2，…，n)。

 (2)从 S 之外的顶点集合 V-S 中选出一个顶点 W，使 dist[W]的值最小。于是，从源点到达 W 只通过 S

中的顶点，我们把 W 加入集合 S。

 (3)调整 dist 中记录的从源点到 V-S 中每个顶点 V 的距离：从原来的 dist[v]和 dist[w]+cost[w，v]中选择

较小的值作为新的 dist[v]。

 (4)重复上述过程(2)和（3），直到 S 中包含 V 的全部顶点。

 最终数组 dist 记录了从源点到 V 中其余各顶点的最短路径。

 对图 3 所示的加权有向图应用 Dijkstra 算法，从源点 V2 出发到达各顶点的最短路径如下表所示。

最短路径

---------------------------------------

源点 中间顶点 终止顶点 长度

3=)!

>)=

其余各顶点的距离：90>1＝)=，为次小，将 > 加入 "。90?1＝03，>180>，?1%)=8)=＝

>!，经中间点 >。"＝&3，=，>，?'，同理，90)1＝03，>180>，)1＝>=，"＝

&3，=，>，?，)'，由于 3 没有一条到 @ 的路径，所以 90@1%。

555由此我们给出最短路径算法如下

<<；9；<；"，!；



54*$%).

590*1$%0!，*1&最短路径初始化值'

55540!，*1,A

555+<0*1$%!；&< 记载当前最短路径'

55555+/$%*；*$%90719

55555&找最小 9071'

555"$%"80/1$%8)&/ 为找到最短路径的终点'

5554*$%).

5554*".90/180/，*1,90*1

555+90*1$%90/180/，*1&调整非 " 集各点最短路径值'

55555<0*1$%/； &调整非 " 集各点最短路径'

5559

555$%8)

59

5555*+(,6!.

555557(；($%<0(19&通过找前趋点，反向输出最短路径'

55557(；7B901

5559

5"7，!；7B;A;9

.；

容易看出，算法 << 的时间复杂度为 