有向图中的顶点，使得存在从这个顶点到另一个顶点的路径

如何找到有向图中的所有顶点，使得每个顶点都可以从这个顶点到达？现在我只能“发明”O（| V |^3）算法 - 来自每个顶点的DFS/BFS，但我相信，存在解决此问题的更快方法。有向图中的顶点，使得存在从这个顶点到另一个顶点的路径

谢谢！

2013-12-23 vortexxx192

运行strongly connected components algorithm将图表折叠为其强连通组件的directed acyclic graph。必须至少有一个强连通的组件，没有传入边缘。如果只有一个，则该组件中的节点就是您正在查找的节点。如果存在多个没有传入边的强连通组件，则不存在所有其他节点都可以到达的节点。

来源

2013-12-23 06:48:32 user2357112

哦，男人，你是天才，这是我一直在寻找的解决方案。谢谢！ – vortexxx192

编辑：见下面的评论！

有时候是关于术语的。这里的魔术字是可达性的（见Wikipedia）。不幸的是，我不认为你会喜欢结果。

如果不是所有的答案都需要，那么实际上建议运行BFS/DFS。
否则，使用Floyd-Warshall算法。仍然运行在O（| V | ）。
特定情况下存在某些优化算法 - 请参阅Wikipedia以获取更多详细信息。

所以这可能不是你想听到的。

来源

2013-12-23 06:52:10

我可能是错的（不是定义为100％），但是这不是解决一个更难的问题（即获得所有顶点之间的可达性，而不是仅仅能够到达所有其他顶点的可达性）吗？按照其他答案中的建议，使用[强连通组件]（http://en.wikipedia.org/wiki/Strongly_connected_component#Algorithms）似乎可以在小于O（| V |^3）的情况下工作。 – Dukeling

是的，我认为你是对的，所以我会upvote其他答案。我今天学了些新东西！你认为@ user2357112的做法是在哪里发布的？他并不是这样称呼它的，它似乎是解决别人可能想要解决的问题的一种非常聪明的方式。 –

有向图中的顶点，使得存在从这个顶点到另一个顶点的路径

回答

相关问题