拓扑排序
一个复杂的工程通常可以分解成一组小使命的聚集，完成这些小使命意味着整个工程的完成。比方，汽车安装工程可分解为以下使命：将底盘放上安装线，装轴，将座位装在底盘上，上漆，装刹车，装门等等。使命之间具有先后干系，比方在装轴之前必需先将底板放上安装线。使命的先后次序可用有向图表示——称为极点活动（ 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）已表示了这种干系。
在许多条件下，使命的实行是一连举行的，比方汽车安装题目或平时购置的标有“必要安装”的消费品（自行车、小孩的秋千安装，割草机等等）。我们可根据所发起的次序来安装。在由使命建立的有向图中，边（ 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 循环的每次迭代代表贪心算法的一个步骤。
现在用贪心算法来求解图1 - 4的有向图。起首从一个空序列V开始，第一步选择V的第一个极点。此时，在有向图中有两个候选极点1和2，若选择极点2，则序列V = 2，第一步完成。第二步选择V的第二个极点，根据贪心准则可知候选极点为1和5，若选择5，则V = 2 5。下一步，极点1是独一的候选，因而V = 2 5 1。第四步，极点3是独一的候选，因而把极点3参加V
失掉V = 2 5 1 3。在末了两步辨别参加极点4和6 ，得V = 2 5 1 3 4 6。
1. 贪心算法的正确性
为保证贪心算法算的正确性，必要证明： 1) 当算法失败时，有向图没有拓扑序列； 2) 若
算法没有失败，V便是拓扑序列。2) 便是用贪心准则来选取下一个极点的直接结果， 1) 的证明见定理1 3 - 2，它证明了若算法失败，则有向图中有环路。若有向图中包含环qj qj + 1.qk qj , 则它没有拓扑序列，由于该序列表示了qj 肯定要在qj 开始前完成。
定理1-2 如果图1 3 - 5算法失败，则有向图含有环路。
证明注意到当失败时| V |
2. 数据结构的选择
为将图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入栈。
步伐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 ]中。
3. Network:Topological 的复杂性
第一和第三个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)。
步伐13-2 拓扑排序
bool Network::Topological(int v[])
{// 计算有向图中极点的拓扑序次
// 如果找到了一个拓扑序次，则前往t r u e，此时，在v [ 0 : n - 1 ]中记载拓扑序次
// 如果不存在拓扑序次，则前往f a l s e
int n = Ve r t i c e s ( ) ;
// 计算入度
int *InDegree = new int [n+1];
InitializePos(); // 图遍历器数组
for (int i = 1; i <= n; i++) // 初始化
InDegree[i] = 0;
for (i = 1; i <= n; i++) {// 从i 出发的边
int u = Begin(i);
while (u) {
I n D e g r e e [ u ] + + ;
u = NextVe r t e x ( i ) ; }
}
// 把入度为０的极点压入货仓
LinkedStack S;
for (i = 1; i <= n; i++)
if (!InDegree[i]) S.Add(i);
// 产生拓扑序次
i = 0; // 数组v 的游标
while (!S.IsEmpty()) {// 从货仓中选择
int w; // 下一个极点
S . D e l e t e ( w ) ;
v[i++] = w;
int u = Begin(w);
while (u) {// 修改入度
I n D e g r e e [ u ] - - ;
if (!InDegree[u]) S.Add(u);
u = NextVe r t e x ( w ) ; }
}
D e a c t i v a t e P o s ( ) ;
delete [] InDegree;
return (i == n);
}
l
- 文章作者: 福州军威计算机技术有限公司
军威网络是福州最专业的电脑维修公司,专业承接福州电脑维修、上门维修、IT外包、企业电脑包年维护、局域网网络布线、网吧承包等相关维修服务。
版权声明：原创作品，允许转载，转载时请务必以超链接形式标明文章原始出处 、作者信息和声明。否则将追究法律责任。
TAG:
|
评论加载中...
|
