graph-algorithm - 令 G 为有向图。有一个特殊的顶点 S 使得从图中的每个其他顶点到该顶点都有一条路径

Question

要检查一个顶点 v 是否是一个特殊的顶点，是否足以表明它在一个 sink 强连通分量中？难道我们不需要证明底层的无向图是连通的吗？如果是这种情况，检查顶点是否特殊的最佳方法是什么

Answer 1

即使我们知道图的无向形式是连通的，仅仅证明 v 在汇 SCC 中是不够的。这是因为可能存在多个接收器 SCC，而一个接收器无法从另一个接收器到达。

如果您的问题是：“给定一个顶点 v，确定 v 是否可以从图中的每个其他顶点到达的最佳方法是什么”，那么您应该从 v 开始并向后跟踪所有边。如果您可以通过向后跟踪边到达每个顶点，那么这意味着 v 可以从图中的每个其他顶点到达。

如果您没有考虑特定的顶点，但想知道是否有任何顶点可以从其他每个顶点到达，则与此问题类似。您使用Tarjan 算法将您的图转换为 SCC 的有向无环图。如果这个图中有一个唯一的 sink SCC，那么这个 sink SCC 中的每个顶点都可以从整个图中的每个顶点到达。如果有多个汇 SCC，则不存在可以从图中的每个其他顶点到达的顶点。