algorithm - 有向图中的顶点存在从这个顶点到每个其他顶点的路径

Question

如何找到有向图中的所有顶点，使得每个其他顶点都可以从这个顶点到达？现在我只能“发明”O(|V|^3) 算法——来自每个顶点的 DFS/BFS，但我敢肯定，有一种更快的方法可以解决这个问题。

谢谢!

Answer 1

运行 strongly connected components algorithm将图表折叠成 directed acyclic graph它的强连接组件。必须至少有一个没有入边的强连通分量。如果恰好有一个，则该组件中的节点就是您要查找的节点。如果存在多个没有传入边的强连通组件，则不存在所有其他节点都可达的节点。