数学建模社区-数学中国

标题: 拓扑排序 [打印本页]
作者: 韩冰    时间: 2004-10-4 05:23
标题: 拓扑排序

一个复杂的工程通常可以分解成一组小任务的集合，完成这些小任务意味着整个工程的完成。例如，汽车装配工程可分解为以下任务：将底盘放上装配线，装轴，将座位装在底盘上，上漆，装刹车，装门等等。任务之间具有先后关系，例如在装轴之前必须先将底板放上装配线。任务的先后顺序可用有向图表示——称为顶点活动（ Activity On Vertex, AOV）网络。有向图的顶点代表任务，有向边(i, j) 表示先后关系：任务j 开始前任务i 必须完成。图1 - 4显示了六个任务的工程，边（ 1 , 4）表示任务1在任务4开始前完成，同样边（ 4 , 6）表示任务4在任务6开始前完成，边（1 , 4）与（4 , 6）合起来可知任务1在任务6开始前完成，即前后关系是传递的。由此可知，边（1 , 4）是多余的，因为边（1 , 3）和（3 , 4）已暗示了这种关系。

# u( f: V h; b

在很多条件下，任务的执行是连续进行的，例如汽车装配问题或平时购买的标有“需要装配”的消费品（自行车、小孩的秋千装置，割草机等等）。我们可根据所建议的顺序来装配。在由任务建立的有向图中，边（ i, j）表示在装配序列中任务i 在任务j 的前面，具有这种性质的序列称为拓扑序列（topological orders或topological sequences)。根据任务的有向图建立拓扑序列的过程称为拓扑排序（topological sorting）。图1 - 4的任务有向图有多种拓扑序列，其中的三种为1 2 3 4 5 6，1 3 2 4 5 6和2 1 5 3 4 6，序列1 4 2 3 5 6就不是拓扑序列，因为在这个序列中任务4在3的前面，而任务有向图中的边为（ 3 , 4），这种序列与边（ 3 , 4）及其他边所指示的序列相矛盾。可用贪婪算法来建立拓扑序列。算法按从左到右的步骤构造拓扑序列，每一步在排好的序列中加入一个顶点。利用如下贪婪准则来选择顶点：从剩下的顶点中，选择顶点w，使得w 不存在这样的入边（ v,w），其中顶点v 不在已排好的序列结构中出现。注意到如果加入的顶点w违背了这个准则（即有向图中存在边（ v,w）且v 不在已构造的序列中），则无法完成拓扑排序，因为顶点v 必须跟随在顶点w 之后。贪婪算法的伪代码如图1 3 - 5所示。while 循环的每次迭代代表贪婪算法的一个步骤。

2 D9 B& B0 V `$ A0 S8 `! V' }& f

现在用贪婪算法来求解图1 - 4的有向图。首先从一个空序列V开始，第一步选择V的第一个顶点。此时，在有向图中有两个候选顶点1和2，若选择顶点2，则序列V = 2，第一步完成。第二步选择V的第二个顶点，根据贪婪准则可知候选顶点为1和5，若选择5，则V = 2 5。下一步，顶点1是唯一的候选，因此V = 2 5 1。第四步，顶点3是唯一的候选，因此把顶点3加入V

5 \6 N: k% x# K# N4 c* v' J+ u

得到V = 2 5 1 3。在最后两步分别加入顶点4和6 ，得V = 2 5 1 3 4 6。

; o, }3 {: C/ T4 ?+ h8 O( x

1. 贪婪算法的正确性

1 w; g, h* F% u% }4 n6 U5 N

为保证贪婪算法算的正确性，需要证明： 1) 当算法失败时，有向图没有拓扑序列； 2) 若

( i: x2 }/ C% d4 d- f- v

算法没有失败，V即是拓扑序列。2) 即是用贪婪准则来选取下一个顶点的直接结果， 1) 的证明见定理1 3 - 2，它证明了若算法失败，则有向图中有环路。若有向图中包含环qj qj + 1.qk qj , 则它没有拓扑序列，因为该序列暗示了qj 一定要在qj 开始前完成。

4 v- l' X8 ^5 ]( m+ c

定理1-2 如果图1 3 - 5算法失败，则有向图含有环路。

& M3 F# m9 M6 [9 G( `

证明注意到当失败时| V | * g' W- D) [" J6 d5 q/ W

2. 数据结构的选择

E( i: W5 s A# {

为将图1 - 5用C + +代码来实现，必须考虑序列V的描述方法，以及如何找出可加入V的候选顶点。一种高效的实现方法是将序列V用一维数组v 来描述的，用一个栈来保存可加入V的候选顶点。另有一个一维数组I n D e g r e e，I n D e g r e e[ j ]表示与顶点j相连的节点i 的数目，其中顶点i不是V中的成员，它们之间的有向图的边表示为（ i, j）。当I n D e g r e e[ j ]变为0时表示j 成为一个候选节点。序列V初始时为空。I n D e g r e e[ j ]为顶点j 的入度。每次向V中加入一个顶点时，所有与新加入顶点邻接的顶点j，其I n D e g r e e[ j ]减1。对于有向图1 - 4，开始时I n D e g r e e [ 1 : 6 ] = [ 0 , 0 , 1 , 3 , 1 , 3 ]。由于顶点1和2的I n D e g r e e值为0，因此它们是可加入V的候选顶点，由此，顶点1和2首先入栈。每一步，从栈中取出一个顶点将其加入V，同时减去与其邻接的顶点的I n D e g r e e值。若在第一步时从栈中取出顶点2并将其加入V，便得到了v [ 0 ] = 2，和I n D e g r e e [ 1 : 6 ] = [ 0 , 0 , 1 , 2 , 0 , 3 ]。由于I n D e g r e e [ 5 ]刚刚变为0，因此将顶点5入栈。

( y0 @, K' P4 M5 \# t8 e

程序1 3 - 2给出了相应的C + +代码，这个代码被定义为N e t w o r k的一个成员函数。而且，它对于有无加权的有向图均适用。但若用于无向图（不论其有无加权）将会得到错误的结果，因为拓扑排序是针对有向图来定义的。为解决这个问题，利用同样的模板来定义成员函数AdjacencyGraph, AdjacencyWGraph，L i n k e d G r a p h和L i n k e d W G r a p h。这些函数可重载N e t w o r k中的函数并可输出错误信息。如果找到拓扑序列，则Topological 函数返回t r u e；若输入的有向图无拓扑序列则返回f a l s e。当找到拓扑序列时，将其返回到v [ 0 :n- 1 ]中。

- r: S- U* g" R" s' M; V

3. Network:Topological 的复杂性

( S+ I" d7 z- a) w/ \. g

第一和第三个f o r循环的时间开销为(n )。若使用（耗费）邻接矩阵,则第二个for 循环所用的时间为(n2 )；若使用邻接链表,则所用时间为(n+e)。在两个嵌套的while 循环中，外层循环需执行n次，每次将顶点w 加入到v 中，并初始化内层while 循环。使用邻接矩阵时，内层w h i l e循环对于每个顶点w 需花费(n)的时间；若利用邻接链表，则这个循环需花费dwout 的时间，因此，内层while 循环的时间开销为(n2 )或(n+e)。所以，若利用邻接矩阵，程序1 3 - 2的时间复杂性为(n2 )，若利用邻接链表则为(n+e)。

; g# ~4 F- C' Z6 J. ~4 P

程序13-2 拓扑排序

6 B: d1 c9 W4 m% I: g" l6 s2 I

bool Network::Topological(int v[])

' K0 ~0 _7 `- R& i

{// 计算有向图中顶点的拓扑次序

- g" L' D! x" H, o8 T" _

// 如果找到了一个拓扑次序，则返回t r u e，此时，在v [ 0 : n - 1 ]中记录拓扑次序

B- }2 c2 j+ r, R: Q- j

// 如果不存在拓扑次序，则返回f a l s e

. S& P# I& x& V+ {! q( `2 `, A7 G

int n = Ve r t i c e s ( ) ;

! g: \& d: @3 V9 D; u# c k

// 计算入度

- B: E* l8 ^* Y g7 Z1 @

int *InDegree = new int [n+1];

- S: g: F3 X, J! N% }7 F1 \. J

InitializePos(); // 图遍历器数组

* ]+ s5 F6 y$ u2 ?: I6 E( v) @

for (int i = 1; i <= n; i++) // 初始化

0 Z& O9 n2 v& ~2 l

InDegree = 0;

# }1 L# G: |, H: y( R, O

for (i = 1; i <= n; i++) {// 从i 出发的边

& I/ D0 L1 M3 N/ w; S/ f( }

int u = Begin(i);

' e. K5 Y1 t0 W) G6 u" V, Y7 i! F

while (u) {

/ J/ l3 Q' a) P0 ~2 l4 ^

I n D e g r e e [ u ] + + ;

9 \& K+ i1 e8 ?, I4 j: L k/ E

u = NextVe r t e x ( i ) ; }

7 h2 f: l, a8 m* o: p9 E! r, I( O2 u

}

% _3 D$ ?1 \0 _/ e) G% W

// 把入度为０的顶点压入堆栈

+ M8 x/ c# W$ [ k6 z+ v# }5 m" U. M3 d

LinkedStack S;

# u! Y8 P9 V4 N8 \3 r

for (i = 1; i <= n; i++)

$ H. a* k+ R- U7 H: G$ `3 {* R

if (!InDegree) S.Add(i);

k2 b6 i7 |9 n) c

// 产生拓扑次序

+ N* c1 Z; C2 ~; {

i = 0; // 数组v 的游标

`0 W+ Z; I/ t0 P

while (!S.IsEmpty()) {// 从堆栈中选择

/ v ]- W) |/ C* r6 f. m- a

int w; // 下一个顶点

. L6 M, }& C N; H4 Y, V

S . D e l e t e ( w ) ;

; T$ m$ u- G% @/ O0 v2 J

v[i++] = w;

+ U9 F& z" w+ r9 ?4 T8 }; e! ?

int u = Begin(w);

- c4 j0 C8 U+ _0 u

while (u) {// 修改入度

- h& Q' i x* Q6 Y2 \

I n D e g r e e [ u ] - - ;

5 i# F4 q/ `/ Y9 q3 r; f3 b

if (!InDegree) S.Add(u);

# w T3 o9 n3 N3 n0 E3 c: [- n A

u = NextVe r t e x ( w ) ; }

$ @# q8 O: l' h7 a- s1 z

}

8 B9 u( L# l Y' q5 P

D e a c t i v a t e P o s ( ) ;

: d) q, Z0 a) a a* Z+ Q% O

delete [] InDegree;

( I8 Q$ _3 G% L, Y; Z0 G1 e

return (i == n);

4 Y/ j" b! y: I; }

}

作者: xiaomeizi    时间: 2010-1-27 21:59
没太看明白！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
作者: weixinmaths    时间: 2011-6-22 16:16
作者: 乱世惊云    时间: 2011-9-8 13:27
赛前恶补一下！！！！！



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5