c语言算法 - 贪婪算法 - 拓扑排序(2)时间:2010-01-28
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 ) ; } } // 把入度为0的顶点压入堆栈 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); } |
|