c语言算法 – 贪婪算法 – 拓扑排序

副标题#e#

一个巨大的工程凡是可以解析成一组小任务的荟萃，完成这些小任务意味着整个工程的完成。譬喻，汽车装配工程可解析为以下任务：将底盘放上装配线，装轴，将座位装在底盘上，上漆，装刹车，装门等等。任务之间具有先后干系，譬喻在装轴之前必需先将底板放上装配线。任务的先后顺序可用有向图暗示——称为极点勾当（ 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 |

#p#副标题#e#

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 的巨大性

#p#分页标题#e#

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