📄 拓扑排序算法.htm
字号:
<TABLE cellSpacing=0 cellPadding=0 width="100%" bgColor=#ffffff
border=0>
<TBODY>
<TR>
<TD width=8 height=0></TD>
<TD width=375></TD>
<TD width=193></TD>
<TD width=2></TD>
<TD width=12></TD></TR>
<TR align=middle>
<TD vAlign=center colSpan=5 height=40><SPAN class=Title
id=_ctl0_TitleLabel>
<P>拓扑排序算法</P></SPAN></TD></TR>
<TR>
<TD vAlign=center align=middle height=28></TD>
<TD vAlign=center align=middle colSpan=2>
<DIV align=right><FONT color=#c0c0c0> 作者：unknown
日期：2005-8-4 19:25:06</FONT> <FONT
color=#c0c0c0>点击：
<SCRIPT src="拓扑排序算法.files/Click.htm"></SCRIPT>
</FONT> </DIV>
<HR width="100%" SIZE=1>
<DIV align=right></DIV></TD>
<TD vAlign=center align=middle colSpan=2> </TD></TR>
<TR>
<TD height=0></TD>
<TD></TD>
<TD></TD>
<TD></TD>
<TD></TD></TR>
<TR>
<TD height=73></TD>
<TD vAlign=top colSpan=2><!---
The site is designed by yuandian. www.it00.com
<TABLE style="TABLE-LAYOUT: fixed; WORD-BREAK: break-all" cellSpacing=0 cellPadding=0 width="100%" border=0>
<TBODY>
<TR>
<TD class=Content></TD></TR>
<TR>
<TD>
--->
<TABLE style="TABLE-LAYOUT: fixed; WORD-BREAK: break-all"
cellSpacing=0 cellPadding=0 width="100%" border=0>
<TBODY>
<TR>
<TD class=Content></TD></TR>
<TR>
<TD>
<P>一个复杂的工程通常可以分解成一组小任务的集合，完成这些小任务意味着整个工程的完成。例如，汽车装配工程可分解为以下任务：将底盘放上装配线，装轴，将座位装在底盘上，上漆，装刹车，装门等等。任务之间具有先后关系，例如在装轴之前必须先将底板放上装配线。任务的先后顺序可用有向图表示——称为顶点活动（
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）已暗示了这种关系。
<BR><BR>在很多条件下，任务的执行是连续进行的，例如汽车装配问题或平时购买的标有“需要装配”的消费品（自行车、小孩的秋千装置，割草机等等）。我们可根据所建议的顺序来装配。在由任务建立的有向图中，边（
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 循环的每次迭代代表贪婪算法的一个步骤。 <BR><BR>现在用贪婪算法来求解图1 -
4的有向图。首先从一个空序列V开始，第一步选择V的第一个顶点。此时，在有向图中有两个候选顶点1和2，若选择顶点2，则序列V
= 2，第一步完成。第二步选择V的第二个顶点，根据贪婪准则可知候选顶点为1和5，若选择5，则V = 2
5。下一步，顶点1是唯一的候选，因此V = 2 5 1。第四步，顶点3是唯一的候选，因此把顶点3加入V
<BR><BR>得到V = 2 5 1 3。在最后两步分别加入顶点4和6 ，得V = 2 5 1 3 4 6。
<BR><BR>1. 贪婪算法的正确性 <BR><BR>为保证贪婪算法算的正确性，需要证明： 1)
当算法失败时，有向图没有拓扑序列； 2) 若 <BR><BR>算法没有失败，V即是拓扑序列。2)
即是用贪婪准则来选取下一个顶点的直接结果， 1) 的证明见定理1 3 -
2，它证明了若算法失败，则有向图中有环路。若有向图中包含环qj qj + 1.qk qj ,
则它没有拓扑序列，因为该序列暗示了qj 一定要在qj 开始前完成。 <BR><BR>定理1-2 如果图1 3 -
5算法失败，则有向图含有环路。 <BR><BR>证明注意到当失败时| V | <BR><BR>2. <A
href="http://www.it00.com/search.asp?condition=title&keyword=数据"
target=_blank>数据</A>结构的选择 <BR><BR>为将图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入栈。 <BR><BR>程序1 3 -
2给出了相应的C + +代码，这个代码被定义为N e t w o r k的一个成员<A
href="http://www.it00.com/search.asp?condition=title&keyword=函数"
target=_blank>函数</A>。而且，它对于有无加权的有向图均适用。但若用于无向图（不论其有无加权）将会得到错误的结果，因为拓扑排序是针对有向图来定义的。为解决这个问题，利用同样的模板来定义成员<A
href="http://www.it00.com/search.asp?condition=title&keyword=函数"
target=_blank>函数</A>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。这些<A
href="http://www.it00.com/search.asp?condition=title&keyword=函数"
target=_blank>函数</A>可重载N e t w o r k中的<A
href="http://www.it00.com/search.asp?condition=title&keyword=函数"
target=_blank>函数</A>并可输出错误信息。如果找到拓扑序列，则Topological <A
href="http://www.it00.com/search.asp?condition=title&keyword=函数"
target=_blank>函数</A>返回t r u e；若输入的有向图无拓扑序列则返回f a l s
e。当找到拓扑序列时，将其返回到v [ 0 :n- 1 ]中。 <BR><BR>3.
Network:Topological 的复杂性 <BR><BR>第一和第三个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)。 <BR><BR>程序13-2 拓扑排序 <BR><BR>bool
Network::Topological(int v[]) <BR><BR>{// 计算有向图中顶点的拓扑次序
<BR><BR>// 如果找到了一个拓扑次序，则返回t r u e，此时，在v [ 0 : n - 1
]中记录拓扑次序 <BR><BR>// 如果不存在拓扑次序，则返回f a l s e <BR><BR>int n
= Ve r t i c e s ( ) ; <BR><BR>// 计算入度 <BR><BR>int
*InDegree = new int [n+1]; <BR><BR>InitializePos(); //
图遍历器数组 <BR><BR>for (int i = 1; i <= n; i++) // 初始化
<BR><BR>InDegree[i] = 0; <BR><BR>for (i = 1; i <= n;
i++) {// 从i 出发的边 <BR><BR>int u = Begin(i); <BR><BR>while
(u) { <BR><BR>I n D e g r e e [ u ] + + ; <BR><BR>u =
NextVe r t e x ( i ) ; } <BR><BR>} <BR><BR>//
把入度为０的顶点压入堆栈 <BR><BR>LinkedStack S; <BR><BR>for (i = 1;
i <= n; i++) <BR><BR>if (!InDegree[i]) S.Add(i);
<BR><BR>// 产生拓扑次序 <BR><BR>i = 0; // 数组v 的游标
<BR><BR>while (!S.IsEmpty()) {// 从堆栈中选择 <BR><BR>int w;
// 下一个顶点 <BR><BR>S . D e l e t e ( w ) ; <BR><BR>v[i++]
= w; <BR><BR>int u = Begin(w); <BR><BR>while (u) {//
修改入度 <BR><BR>I n D e g r e e [ u ] - - ; <BR><BR>if
(!InDegree[u]) S.Add(u); <BR><BR>u = NextVe r t e x ( w
) ; } <BR><BR>} <BR><BR>D e a c t i v a t e P o s ( ) ;
<BR><BR>delete [] InDegree; <BR><BR>return (i == n);
<BR><BR>}</P></TD></TR>
<TR>
<TD align=right><SPAN id=_ctl0_PageList>上一篇：<A
title=数据结构算法集---C++语言实现
href="http://www.it00.com/news/program/vc15/05841938101810.htm">数据结构算法集---C++语言实现</A> 下一篇：<A
title=各种排序算法小结
href="http://www.it00.com/news/program/vc15/058419381122940.htm">各种排序算法小结</A></SPAN></TD></TR>
<TR>
<TD align=right height=10> </TD></TR></TBODY></TABLE></TD>
<TD></TD>
<TD></TD></TR>
<TR>
<TD></TD>
<TD vAlign=center colSpan=2>
<SCRIPT src="拓扑排序算法.files/2.js"></SCRIPT>
</TD>
<TD></TD>
<TD></TD></TR>
<TR>
<TD height=10></TD>
<TD vAlign=center colSpan=2></TD>
<TD></TD>
<TD></TD></TR>
<TR>
<TD height=108></TD>
<TD vAlign=top colSpan=3>
<TABLE height=100 cellSpacing=1 cellPadding=5 width=580
bgColor=#e6e6e6 border=0>
<TBODY>
<TR>
<TD align=middle width="4%" bgColor=#f8f8f6 height=10><A
href="http://www.it00.com/map.asp"
target=_blank><B>站<BR>点<BR>地<BR>图</B></A></TD>
<TD bgColor=#ffffff>
<DIV id=_ctl0_RemarkNoData style="TEXT-ALIGN: left">
<P>
<TABLE cellSpacing=0 cellPadding=0 width="100%"
border=0>
<TBODY>
<TR>
<TD>【<B><A
href="http://www.it00.com/news/os/index.html">操作系统</A></B>】 【<B><A
href="http://www.it00.com/news/program/index.html">程序设计</A></B>】 【<B><A
href="http://www.it00.com/news/graphics/index.html">图形图像</A></B>】 【<B><A
href="http://www.it00.com/news/mediamovice/index.html">媒体动画</A></B>】 【<B><A
href="http://www.it00.com/news/machine/index.html">机械电子</A></B>】 【<B><A
href="http://www.it00.com/news/web/index.html">WEB开发</A></B>】 <BR>【<B><A
href="http://www.it00.com/news/database/index.html">数
据 库</A></B>】 【<B><A
href="http://www.it00.com/news/office/index.html">办公系列</A></B>】 【<B><A
href="http://www.it00.com/news/router/index.html">路由技术</A></B>】 【<B><A
href="http://www.it00.com/news/netyl/index.html">网络原理</A></B>】 【<B><A
href="http://www.it00.com/news/netapp/index.html">网络应用</A></B>】 【<B><A
href="http://www.it00.com/news/cert/index.html">认证考试</A></B>】 <BR>【<B><A
href="http://www.it00.com/news/safe/index.html">安全技术</A></B>】 </TD></TR></TBODY></TABLE></P></DIV></TD></TR></TBODY></TABLE></TD>
<TD></TD></TR></TBODY></TABLE></TD></TR>
<TR>
<TD bgColor=#e6e6e6><BR>Copyright ©2005 - 2008 <A
href="http://www.it00.com/"><FONT face=Verdana, size=1 sans-serif
Helvetica, Arial,><B>IT00<FONT
color=#cc0000>.COM</FONT></B></FONT></A>，All Rights Reserved
<SCRIPT language=JavaScript src="拓扑排序算法.files/stat.htm"
charset=gb2312></SCRIPT>
</TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -