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

核心提示：2. 数据结构的选择为将图1 - 5用C + +代码来实现，必须考虑序列V的描述方法，c语言算法 - 贪婪算法 - 拓扑排序(2)，以及如何找出可加入V的候选顶点，一种高效的实现方法是将序列V用一维数组v 来描述的，则返回t r u e，此时，用一个栈来保存可加入V的候选顶点，另有一个一维数组I n D e g r 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 的复杂性

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