在寻找强连通分量的Kosaraju算法中，按完成次数递减的顺序进行DFS有什么必要？
我正在学习寻找强连通分量的Kosaraju算法。
但我不明白上面第三点提到的按完成时间递减的顺序做dfs(G^t)的必要性。
共有1个答案
考虑一个简单的图，它有两个顶点a和B，一条边从B到a（或G^T中的a到B）。如果你在顶点上按A然后B的顺序做dfs(G^t)，那么你就把它输出为一个单强连通分量。而它应该是两个独立的组成部分。
非正式地，按指定顺序执行顶点的必要性是为了确保当您也可以首先执行“向下”G链接时，您只能执行“向上”G链接。
-
我想在无向图中找到一个强连通分量，即如果我从一个节点开始，那么我将回到节点，并且每个边都被精确地访问一次。 对于有向图，可以用Tarjan算法求强连通分量，但是对于无向图，该怎么办。
-
我在读关于BFS和DFS的图算法。当我在分析用DFS寻找图中强连通分量的算法时，我产生了一个疑问。为了寻找强连通分量，book（Coremen）首先在图上运行DFS，以得到顶点的完成时间，然后在图的转置上按照第一个DFS得到的完成时间的递减顺序运行DFS。但是我不能理解为什么第二个DFS必须按照完成时间运行。我的意思是，即使我们直接在图的转置上运行DFS（忽略完成时间），它也会给我们连接的组件吗？
-
我的书定义了一种在线性时间内寻找有向图强连通分量的方法。另外，其他几种寻找强连通分量的算法（如Tarjan算法）也能在线性时间内找到强连通分量。
-
到目前为止，我已经使用了下面的算法来寻找图的强连通分量。 > 调用DFS(G)计算每个顶点v的完成时间F[v]，对G的顶点按完成时间递减的顺序排序； 计算G的转置GT；
-
Kosaraju算法 问题： 用Kosaraju算法求有向图(G)的强连通分支。 解法： Kosaraju算法分为3个步骤： ((1))求出图(G)的逆图(G’)； ((2))求出逆图(G’)的拓扑排序(T)； ((3))按照逆图(G’)拓扑排序(T)的顺序，对原图(G)中每个节点进行DFS，得到的森林即为所求的强连通分支。注意每个节点只能属于一个强连通分支，因此当一个节点被DFS遍历到后，需要将
-
我正在努力自学图论，现在试图理解如何在图中找到SCC。我读过关于SO的几个不同的问题/答案（例如，1、2、3、4、5、6、7、8)，但我找不到一个可以遵循的完整的一步一步的例子。 根据CORMEN（算法导论），一种方法是： 调用DFS(G)计算每个顶点u的完成时间f[u] 计算转置(G) 调用DFS（转置(G))，但在DFS的主循环中，按F[u]递减的顺序考虑顶点（如步骤1中计算的那样） 输出步骤