algorithm - 确定有向图是否是单边的

Question

您将如何确定有向图是否是单边的(对于任何一对顶点 u、v，至少一个可以从另一个到达)？我认为您可以运行 DFS 或 BFS 并查看是否可以到达每个顶点。如果不是，则计算转置并从同一顶点执行相同的搜索算法。如果你至少到达了每个顶点，那么这个图是单边的吗？

显然，您可以通过分析邻接矩阵在较长的运行时间内完成此操作，但理想情况下我们希望在 O(V+E) 中运行

Answer 1

尝试 these algorithms .我在大学里学的是 Floyd-Warshall，但是它的性能并没有你想要的那么好。 Johnsons's algorithm对于稀疏图更快，但仍然是 O(V*E)，而不是 O(V+E)。