图论算法集锦
§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 个顶点的连通图,至少有 n-1 条边,而生成树中恰好有 n-1 条边,所以连通
图的生成树是该图的极小连通子图。若图 G 的生成树中任意加一条边属于边集 B(G)中
的边,则必然形成回路。
求解生成树在许多领域有实际意义。例如,对于供电线路或煤气管道的铺设问题,
即假设要把 n 个城市联成一个供电或煤气管道网络,则需要铺设 n-1 条线路。任意两
城市间可铺设一条线路,n 个城市间最多可能铺设 n(n-1)/2 条线路,各条线路的造价
一般是不同的。一个很实际的问题就是如何在这些可能的线路中选择 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 个居民点,又能使
总的花费代价最小。
解决上述问题的数学模型就是求图中网的最小生成树问题。把居民点看作图的顶点,
把居民点之间的煤气管道看作边,而把敷设各条线路的代价当作权赋给相应的边。这样,
便构成一个带权的图,即网。对于一个有 n 个顶点的网可以生成许多互不相同的生成树,
每一棵生成树都是一个可行的敷设方案。现在的问题是应寻求一棵所有边的权总和为最
小的生成树。
如何构造这种网的最小生成树呢?下面给出这样一种解法:
(1)已知一个网,将网中的边按其权值由小到大的次序顺序选取。
(2)若选某边后不形成回路,则将其保留作为树的一条边;若选某边后形成回路,则
将其舍弃,以后也不再考虑。
(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),(2,4)时均无问题,保留作为树的边;到第 3 条边(4,3)时将与已
保留的边形成回路,将其舍去;同样继续做:保留(2, 6);舍去(6,4);保留(5,7),
(1,5),(1,6),此时,保留的边数已够(n-1)=6 条边,此时必定将 7 个顶点全部互相连
通了,后面剩下的边(1,2),(5,6)就不必再考虑了。最后得到的最小生成树如图 2a 中
深色边所示,其各边权值总和等于 80。由离散数学中的图论可以证明,这就是最小生
成树了,其权值最小。当图中有权值相等的边时,其最小生成树可能有不同的选取方案。
实现此算法的关键是,在选取某条边时应判断是否与已保留的边形成回路。
这可用将各顶点划分为集合的办法解决:假设数组 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 的变化过程,很容易判断,选择一条新的边是否构成回路。当
新选边的两个顶点 u、v,若 tag[u]和 tag[v]相同并且均不等于 0 时,即 u,v 已在生成
树集合中被保留过,加入 u,v 后即形成回路,不能选。而当 tag [u]<>tag[v]或者 tag[u]
=tag[v]=0 时,可以选并且不形成回路,说明 u,v 中至少有一个顶点未被选过或者被
选过的 u、v 分别属于两个不同的集合,此时选择 u,v 可以将含 u 的集合与含 v 的集合
连通,修改 tag 数组。如此下去,到所有顶点均已属于一个集合时,此最小生成树就完
全构成了。
网的最小生成树算法描述如下:
假设算法中用到的数据结构是经过处理的。
COST(1..n,1..n)是带权数组存放网中顶点之间的权。EV(1..n*(n-1/2))按权从小到大
存放排序后的顶点对,即 EV[K].P1 存放一个顶点,边的另一顶点存放在 EV[K].P2 之中。
tag(1..n):顶点集合划分标志的数组。
Enumb:当前生成树的边数。
SM:当前权累计和。
PROC minspanningtree(VAR cost;VAR ev);
Var tag;
BEGIN
CALL INITIAL(tag);
Enumb:=0;SM:=0; {诸参量初始化}
k:=1; {边数累计}
WHILE (Enumb<=n-1) AND (k<=n) DO
Begin U:=EV[k].P1;V:=EV[k].P2; {选一对顶点(U,V)}
CALL FIND(U,T); {找到含顶点 U 的集合 T}
CALL FIND(V,W); {找到含顶点 V 的集合 W}
IF (T<>W) THEN
Begin
write(u,v);Enumb:=Enumb+1; {最小生成树增加一条边}
SM:=SM+COST[u,v];
MERGE(T,W);{选 u,v 不会形成环,合并 T,W 集合,并修改 tag}
end
K:=K+1; {找下一条边}
end
IF Enumb<n-1 THEN write('There is not a minspanning tree')
ELSE write(SM)
END;
由算法可知图 2 的最小生成树的结果是(2,3),(2,4),(2,6),(5,7),(1,5),(1,
6)。
§2 最短路径
在一个赋权有向图上寻找最短路径问题也是图应用的一个重要课题。
假定图 3 中的有向图 G=(V,E)是一个航空图,V 的每一顶点表示—个城市,正中的
每条弧 v—>w 表示从城市 v 到城市 W 的航线,弧 V—>w 上的标号代表从 V 城飞到 w
评论0