graph - 彼此可达的顶点

Question

给定一个有向图，我需要找到所有顶点 v，这样，如果 u 可以从 v 到达，那么 v 也可以从 u 到达。我知道，可以使用 BFS 或 DFS 找到顶点，但它似乎效率低下。我想知道这个问题是否有更好的解决方案。任何帮助，将不胜感激。

Answer 1

从根本上说，您不会比某种搜索做得更好（正如您所提到的）。我不会太担心效率：这些算法在节点+边的数量上通常是线性的。

问题有点不明确，所以我将对您的数据结构做出一些假设：

1. 你知道顶点 u（因为你没有要求找到它）
2. 您可以（有效地）迭代节点的入站和出站边缘
3. 您可以迭代图中的所有节点
4. 您可以（有效地）将几位数据与每个节点相关联

在这种情况下，使用从顶点 u（深度/宽度，无关紧要）开始的便捷搜索两次：一次跟随出站边（将节点标记为“从 u 可达”）和一次跟随入站边（将节点标记为“到达你”）。最后，遍历所有节点并根据您的目的比较这两位。

注意：按照措辞，您的结果集包括所有未到达顶点 u 的节点。如果您打算使用连词而不是暗示，那么您可以通过在第二次搜索中合并测试来节省一点时间，而不是扫描图中的所有节点。这也减轻了假设 3。