algorithm - 有向图上的 DFS 和 Kosaraju 算法

Question

我无法理解 Kosaraju 用于查找有向图的强连通分量的算法。这是我笔记本上的内容(我是学生 :D):

1. 从任意顶点开始(用#1 标记)并执行 DFS。当你不能再进一步时，用 #2 标记最后访问的顶点，并开始另一个 DFS(跳过已经标记的顶点)，依此类推。
2. 转置图形。
3. 从每个顶点开始按倒序进行DFS，每次DFS结束访问的那些顶点属于同一个SCC。

我有这个例子:

从E开始的第一步之后，标签是:

1. E
2. G
3. K
4. J
5. 我
6. H
7. F
8. C
9. D
10. B
11. 一个

所以问题来了:DFS 在有向图/无向图中有区别吗？我对我脑海中的第一步进行了心理测试，忽略了箭头(就像它是无方向的)并且只得到正确的 E(当然)#1 和 G 的#2，但#3 落在 J 上，而不是 K。所以我想也许我应该尊重箭头，并考虑到这一点做了一个 DFS，但是在从 E 开始的第一遍之后，我不能从 G(#2)去任何地方，所以我被困在那里。

有向图上的 DFS 有什么我不知道的吗？我只在无向图上学习 DFS!

Answer 1

您的第二步未完成。参见 Wikipedia :

Kosaraju's algorithm works as follows:

• Let G be a directed graph and S be an empty stack.
• While S does not contain all vertices:
  • Choose an arbitrary vertex v not in S. Perform a depth-first search starting at v. Each time that depth-first search finishes expanding a vertex u, push u onto S.
• Reverse the directions of all arcs to obtain the transpose graph.
• While S is nonempty:
  • Pop the top vertex v from S. Perform a depth-first search starting at v in the transpose graph. The set of visited vertices will give the strongly connected component containing v; record this and remove all these vertices from the graph G and the stack S. Equivalently, breadth-first search (BFS) can be used instead of depth-first search.

所以你不应该只对最后一个顶点和第一个顶点做一些事情，而应该对 DFS 中的每个顶点做一些事情。

另请注意，您应该是 backtracking - 当你不能走得更远时，你会转到前一个顶点并从那里继续。

不，您不能将其视为无向图 - 边的方向非常重要。

因此，例如，从 E 开始，您将转到 F，然后是 G，然后回到 F ，然后是 H，然后是 K，然后是 I，然后是 J，然后回到 >I、K、H、F，最后是E，压入了所有访问过的顶点入栈。