使用强连接组件Algo检查顶点是否可达

Question

我想看看一个给定的顶点,比如V0,是否可以通过图G中的所有其他顶点到达.
我知道我可以遍历图中的每个顶点并执行BFS/DFS以查看V0是否可达.
但是,这似乎效率很低.

我想知道我是否在图上做了SCC算法,如果v0是所有scc的一部分,那么我可以安全地得出结论v0可以通过所有顶点到达？这将是很好的,因为SCC的成本仅为与Tarjan的O(V + E)并且检查v0是否是scc的一部分也将花费线性时间.

我认为这是有道理的,因为SCC意味着顶点是可达的.对这个逻辑的任何确认？

或任何有效的方法？

Answer 1

V0可能不属于SCC,但仍可通过所有其他顶点访问.举例来说,顶点d上图是所有其它顶点可达,但唯一不平凡的SCC包含顶点a,b,c并且不包含顶点d.

要检查所有其他顶点是否可以访问V0,可以反转每个边的方向(线性时间),然后使用BFS/DFS,从V0开始,检查是否每个其他顶点都可以从V0到达(也是在线性时间内) .