在一个有向图中找到所有其他顶点都可以到达的顶点

本文介绍了在一个有向图中找到所有其他顶点都可以到达的顶点的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

给出一个有向图，我们如何确定是否存在一个顶点v，所有其他顶点都可以从该顶点到达。

如果我们要检查给定的顶点，我知道该怎么做。我们可以在反向图中执行dfs。但是对于这个问题，对图中的每个顶点执行此操作似乎效率低下。

有更好的方法吗？

解决方案

使用 Kosaraju的算法在时间 O（| V | + | E |）中找到图的强连通组件。然后，如果您将每个组件缩小到单个节点，则会留下有向无环图。存在一个顶点，并且仅当DAG中存在一个正好是in度为0的顶点时，才能从该顶点到达所有其他顶点。这就是您要寻找的顶点-所谓的母顶点。 p>

注意：最初建议使用塔里安算法来回答这个问题。 Tarjan的速度可能会快一些，但也比Kosaraju的速度复杂一些。

Given a directed graph, how can we determine whether or not there exists a vertex v, from which all other vertices are reachable. the algorithm should be as efficient as possible.

I know how to do it if we are checking for a given vertex; we could do dfs on the reverse graph. But for this question, it seems inefficient to do it for every vertex in the graph.

Is there a better way?

解决方案

Use Kosaraju's algorithm to find the strongly connected components of the graph in time O(|V|+|E|). If you then "shrink" each component to a single node, you'll be left with a directed acyclic graph. There exists a vertex from which all others can be reached if and only if there is exactly one vertex in the DAG with in-degree 0. This is the vertex you're looking for - the so-called "mother vertex".

Note: This answer originally recommended using Tarjan's algorithm. Tarjan's is likely to be a bit faster, but it's also a bit more complex than Kosaraju's.