QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 6556|回复: 3
打印 上一主题 下一主题

拓扑排序

[复制链接]
字体大小: 正常 放大
韩冰        

823

主题

3

听众

4048

积分

我的地盘我做主

该用户从未签到

发帖功臣 元老勋章

跳转到指定楼层
1#
发表于 2004-10-4 05:23 |只看该作者 |倒序浏览
|招呼Ta 关注Ta

一个复杂的工程通常可以分解成一组小任务的集合,完成这些小任务意味着整个工程的完成。例如,汽车装配工程可分解为以下任务:将底盘放上装配线,装轴,将座位装在底盘上,上漆,装刹车,装门等等。任务之间具有先后关系,例如在装轴之前必须先将底板放上装配线。任务的先后顺序可用有向图表示——称为顶点活动( 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)已暗示了这种关系。

r; o# l# o# Z' |

在很多条件下,任务的执行是连续进行的,例如汽车装配问题或平时购买的标有“需要装配”的消费品(自行车、小孩的秋千装置,割草机等等)。我们可根据所建议的顺序来装配。在由任务建立的有向图中,边( 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 循环的每次迭代代表贪婪算法的一个步骤。

]$ k6 o# [* v2 v7 f' |* k

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

! p% b8 Y" x( W. }! E, Q

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

, e: i9 N4 P3 j$ u' }- d! D

1. 贪婪算法的正确性

+ l! t z# t" n7 h" }9 C' P

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

- A& P; a/ X: @! M

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

6 k, w6 @% r7 J7 k

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

+ [( \/ P* P3 f8 n! Q" [

证明注意到当失败时| V | & {1 { D4 R! m7 i2 r# {- S

2. 数据结构的选择

$ n$ V7 l# P" ]2 _ U: h9 v8 j7 Y

为将图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入栈。

" S; K( B* ?5 C# e$ V" l' W

程序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 ]中。

6 q, y2 L! m5 \# ^% A P: o4 \

3. Network:Topological 的复杂性

# M% b/ U! {' _/ {

第一和第三个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)。

7 C, `. b4 b6 Y8 ?5 a

程序13-2 拓扑排序

" J" H1 ?! i* S% _3 q! K- d% D

bool Network::Topological(int v[])

4 G4 k4 y1 q6 Z( ?5 B

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

, i$ r, j7 A$ d, e1 j

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

1 _$ Z6 ^+ O7 X- O8 P( K! p

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

+ t8 k/ g& Y8 C6 m

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

) Z3 C$ K5 y$ b% H9 ]5 y

// 计算入度

w0 \ v: u+ D/ s% K

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

/ k6 h9 s. O9 X6 W! w3 R

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

c: z" s3 Q) z7 k

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

8 L* L$ L) h, B* m1 L* d

InDegree = 0;

, c! [+ u4 F3 b( @3 k1 y' ?8 `% N

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

. J# h: ~; Y* ^' C; p0 Q/ i; }0 P

int u = Begin(i);

' ^) l* U5 B1 d% X& i

while (u) {

; F) t3 v6 i1 ?; K" Y: b {: l

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

0 |/ S4 L0 w1 |

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

$ a, ?+ \4 u, r/ L- L- ?7 S. p2 y& {

}

0 h' S8 W" d9 I

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

5 M" q0 e1 j! Y' h8 j3 E$ S

LinkedStack S;

. N# a, p& t3 |3 ]

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

# O" K i |& E9 [; s/ [# m

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

- }! h, r/ x( P( w6 F8 E$ X* ] D

// 产生拓扑次序

: G6 s3 k! D% U" D8 u7 O

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

" K- \8 e3 i0 N. w q; A& e

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

1 ^/ J/ l l3 g

int w; // 下一个顶点

, {7 K+ f, S- m( P5 L

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

4 ?2 w& [$ p- H1 Q' Q; s

v[i++] = w;

+ q3 ?) i' k- E y

int u = Begin(w);

, Y, m8 Q: k8 G' Q/ ~8 q4 N

while (u) {// 修改入度

4 m9 l/ R, D. v& T9 o q6 `5 m9 @/ U

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

: _1 g- i0 L2 u3 O& N

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

1 ?: D/ ~/ T9 e4 f; Z. n

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

. w0 [5 {) B3 k. u' N0 L

}

' [+ c$ N: z E S/ L* ?

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

6 N7 \+ s8 g& H6 p+ e" ^

delete [] InDegree;

/ N, }$ g* ?. e& o% D: v

return (i == n);

( x% `8 b1 z7 ? u

}

zan
转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
xiaomeizi 实名认证       

0

主题

3

听众

97

积分

升级  96.84%

该用户从未签到

自我介绍
我是一个贪玩的孩子啊
没太看明白!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
回复

使用道具 举报

1

主题

9

听众

297

积分

升级  98.5%

  • TA的每日心情
    开心
    2024-9-1 01:07
  • 签到天数: 34 天

    [LV.5]常住居民I

    群组数学建模培训课堂2

    回复

    使用道具 举报

    0

    主题

    3

    听众

    454

    积分

    升级  51.33%

  • TA的每日心情
    慵懒
    2014-3-18 21:46
  • 签到天数: 147 天

    [LV.7]常住居民III

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2025-7-15 07:37 , Processed in 0.601565 second(s), 69 queries .

    回顶部