algorithm - 为有向图中的每个顶点查找可达顶点

Question

我知道执行此操作的蛮力方法是对图的所有顶点执行 DFS。因此对于此算法，复杂度为 O(V|V+E|)。但是有没有更有效的方法来做到这一点？

Answer 1

我从像 http://research.microsoft.com/pubs/144985/todsfinal.pdf 这样的论文中得到了印象在一般情况下，没有比 O(VE) 或 O(V^3) 更好的算法。对于稀疏图和其他特殊图，有更快的算法。但是，如果您对将对数据进行的查询数量有一些了解，您似乎仍然可以通过将“索引构造”与“查询”分开来进行改进。如果有很多查询，如果所有数据都预先计算(DFS 或 Floyd-Warshall 等)并存储在 中，则 O(1) 的查询是可能的O(n^2) 空间。另一方面，如果查询相对较少，则可以以查询时间为代价来减少空间和/或索引构建时间。