一个复杂的工程通常可以分解成一组小任务的集合完成这些小任务意味着整个工程的完成例如汽车装配工程可分解为以下任务将底盘放上装配线装轴将座位装在底盘上上漆装剎车装门等等任务之间具有先后关系例如在装轴之前必须先将底板放上装配线任务的先后顺序可用有向图表示——称为顶点活动( Activity On Vertex AOV)网络有向图的顶点代表任务有向边(i j) 表示先后关系任务j 开始前任务i 必须完成图 显示了六个任务的工程边( )表示任务在任务开始前完成同样边( )表示任务在任务开始前完成边( )与( )合起来可知任务在任务开始前完成即前后关系是传递的由此可知边( )是多余的因为边( )和( )已暗示了这种关系
在很多条件下任务的执行是连续进行的例如汽车装配问题或平时购买的标有需要装配的消费品(自行车小孩的秋千装置割草机等等)我们可根据所建议的顺序来装配在由任务建立的有向图中边( i j)表示在装配序列中任务i 在任务j 的前面具有这种性质的序列称为拓扑序列(topological orders或topological sequences)根据任务的有向图建立拓扑序列的过程称为拓扑排序(topological sorting)图 的任务有向图有多种拓扑序列其中的三种为 和 序列 就不是拓扑序列因为在这个序列中任务在的前面而任务有向图中的边为( )这种序列与边( )及其他边所指示的序列相矛盾可用贪婪算法来建立拓扑序列算法按从左到右的步骤构造拓扑序列每一步在排好的序列中加入一个顶点利用如下贪婪准则来选择顶点从剩下的顶点中选择顶点w使得w 不存在这样的入边( vw)其中顶点v 不在已排好的序列结构中出现注意到如果加入的顶点w违背了这个准则(即有向图中存在边( vw)且v 不在已构造的序列中)则无法完成拓扑排序因为顶点v 必须跟随在顶点w 之后贪婪算法的伪代码如图 所示while 循环的每次迭代代表贪婪算法的一个步骤
现在用贪婪算法来求解图 的有向图首先从一个空序列V开始第一步选择V的第一个顶点此时在有向图中有两个候选顶点和若选择顶点则序列V = 第一步完成第二步选择V的第二个顶点根据贪婪准则可知候选顶点为和若选择则V = 下一步顶点是唯一的候选因此V = 第四步顶点是唯一的候选因此把顶点加入V 得到V = 在最后两步分别加入顶点和 得V =
贪婪算法的正确性
为保证贪婪算法算的正确性需要证明 ) 当算法失败时有向图没有拓扑序列; ) 若算法没有失败V即是拓扑序列) 即是用贪婪准则来选取下一个顶点的直接结果 ) 的证明见定理 它证明了若算法失败则有向图中有环路若有向图中包含环qj qj + qk qj 则它没有拓扑序列因为该序列暗示了qj 一定要在qj 开始前完成
定理 如果图 算法失败则有向图含有环路
证明注意到当失败时| V |<>
数据结构的选择
为将图 用C + +代码来实现必须考虑序列V的描述方法以及如何找出可加入V的候选顶点一种高效的实现方法是将序列V用一维数组v 来描述的用一个栈来保存可加入V的候选顶点另有一个一维数组I n D e g r e eI n D e g r e e[ j ]表示与顶点j相连的节点i 的数目其中顶点i不是V中的成员它们之间的有向图的边表示为( i j)当I n D e g r e e[ j ]变为时表示j 成为一个候选节点序列V初始时为空I n D e g r e e[ j ]为顶点j 的入度每次向V中加入一个顶点时所有与新加入顶点邻接的顶点j其I n D e g r e e[ j ]减对于有向图 开始时I n D e g r e e [ : ] = [ ]由于顶点和的I n D e g r e e值为因此它们是可加入V的候选顶点由此顶点和首先入栈每一步从栈中取出一个顶点将其加入V同时减去与其邻接的顶点的I n D e g r e e值若在第一步时从栈中取出顶点并将其加入V便得到了v [ ] = 和I n D e g r e e [ : ] = [ ]由于I n D e g r e e [ ]刚刚变为因此将顶点入栈
程序 给出了相应的C + +代码这个代码被定义为N e t w o r k的一个成员函数而且它对于有无加权的有向图均适用但若用于无向图(不论其有无加权)将会得到错误的结果因为拓扑排序是针对有向图来定义的为解决这个问题利用同样的模板来定义成员函数AdjacencyGraph AdjacencyWGraphL 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 [ :n ]中
Network:Topological 的复杂性
第一和第三个f o r循环的时间开销为(n )若使用(耗费)邻接矩阵则第二个for 循环所用的时间为(n );若使用邻接链表则所用时间为(n+e)在两个嵌套的while 循环中外层循环需执行n次每次将顶点w 加入到v 中并初始化内层while 循环使用邻接矩阵时内层w h i l e循环对于每个顶点w 需花费(n)的时间;若利用邻接链表则这个循环需花费dwout 的时间因此内层while 循环的时间开销为(n )或(n+e)所以若利用邻接矩阵程序 的时间复杂性为(n )若利用邻接链表则为(n+e)
程序 拓扑排序
bool Network::Topological(int v[])
{// 计算有向图中顶点的拓扑次序
// 如果找到了一个拓扑次序则返回t r u e此时在v [ : n ]中记录拓扑次序
// 如果不存在拓扑次序则返回f a l s e
int n = Ve r t i c e s ( ) ;
// 计算入度
int *InDegree = new int [n+];
InitializePos(); // 图遍历器数组
for (int i = ; i <= n; i++) // 初始化
InDegree[i] = ;
for (i = ; 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 = ; i <= n; i++)
if (!InDegree[i]) SAdd(i);
// 产生拓扑次序
i = ; // 数组v 的游标
while (!SIsEmpty()) {// 从堆栈中选择
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) SAdd(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);
}
