寻找在迪图的强连通分量在一个DFS [英] Finding the strongly connected components in a Di-Graph in one DFS
问题描述
现在，我已经使用以下算法查找图表的强连通分量。
By now, I have used the following algorithm for finding the strongly connected components of a graph.
-
调用DFS（G）来计算完成时间F [V]每一个顶点v，以减少他们的整理时间顺序的G的顶点进行排序;
call DFS(G) to compute the finishing time f[v] for every vertex v, sort the vertices of G in decreasing order of their finishing time;
计算的G的转GT;
执行另一个DFS上G，此时在主for循环，我们去到G的顶点 在f的递减顺序[V];
Perform another DFS on G, this time in the main for-loop we go through the vertices of G in the decreasing order of f[v];
输出在DFS林（由第二DFS形成的）每个树的顶点作为一个单独的 强连通分量。
output the vertices of each tree in the DFS forest (formed by the second DFS) as a separate strongly connected component.
不过，我想知道是否有可能找到所有的强连接组件的只有一个DFS。
But I was wondering if it is possible to find all the strongly connected components in only one DFS.
任何帮助在这方面将是非常美联社preciated。
Any help in this regard would be highly appreciated.
推荐答案
查看，算法设计手册由史蒂芬Skiena。它计算SCC在一个DFS。它是基于最古老的可到达顶点的概念。
Check out, Algorithm Design Manual by Steven Skiena. It calculates SCC in one DFS. It's based on the concept of oldest reachable vertex.
初始化每个顶点的可到达的顶点和SCComponent＃本身的开端。
Initialize each vertex's reachable vertex and SCComponent# to itself in the beginning.
low[i] = i;
scc[i] = -1;
做一个DFS有向图，你只在背面边缘和交叉边缘，因为这两个边缘将告诉你，如果你已经遭遇了来自另一背部边缘，进入1部分感兴趣。
Do a DFS on the digraph, you are interested only in back edges and cross edges because these two edges will tell you if you've encountered a back edge and entering 1 component from another.
int edge_classification(int x, int y)
{
if (parent[y] == x) return(TREE);
if (discovered[y] && !processed[y]) return(BACK);
if (processed[y] && (entry_time[y]>entry_time[x])) return(FORWARD);
if (processed[y] && (entry_time[y]<entry_time[x])) return(CROSS);
printf("Warning: unclassified edge (%d,%d)\n",x,y);
}
所以，当你遇到这些边缘，您将到达顶点[]递归的基础上，进入次。 如果（类== BACK）{ 如果（entry_time [Y]＆LT; entry_time [低[X]） 低[X] = Y; }
So when you encounter these edges, you set reachable vertex[] recursively, based on the entry times. if (class == BACK) { if (entry_time[y] < entry_time[ low[x] ] ) low[x] = y; }
if (class == CROSS)
{
if (scc[y] == -1) /* component not yet assigned */
if (entry_time[y] < entry_time[ low[x] ] )
low[x] = y;
}
一个新的强连接组件被发现时的最低到达顶点，从顶点'V'本身（循环可以说，A-> B-> C->一中，最低可达顶点是）。
A new strongly connected component is found whenever the lowest reachable vertex from vertex 'v' is itself (loop can say, a->b->c->a, lowest reachable vertex of a is a).
process_vertex_early(int v)
{
push(&active,v);
}
DFS后一个顶点完成（DFS它的邻居们已经完成过），检查最低到达顶点吧：
After DFS for a vertex is complete (DFS for it's neighbors would have been completed too), check the lowest reachable vertex for it:
if (low[v] == v)
{ /* edge (parent[v],v) cuts off scc */
pop_component(v);
}
if (entry_time[low[v]] < entry_time[low[parent[v]]])
low[parent[v]] = low[v];
pop_component（...）刚刚从栈中弹出，直到该组件被找到。如果A-> B-> C->一扫描堆栈将有一个（底部） - > B-> C（上）..流行，直到顶点'一'看到。你得到一个SCC对'一个'..，同样你得到所有连接组件在一个DFS。
pop_component(...) just pops from the stack until this component is found. If a->b->c->a is scanned the stack will have a(bottom)->b->c(top).. pop until vertex 'a' is seen. You get an SCC for 'a'..and similarly you get all connected components in one DFS.
这篇关于寻找在迪图的强连通分量在一个DFS的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
