图 - 找到顶点从所有其它顶点可达 [英] Graph - find vertex reachable from all other vertices

问题描述

给定一个图，我们怎样才能判断是否存在一个顶点v，使所有其它顶点可达。该算法应该是尽可能高效

Given a 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.

我知道如何做到这一点，如果我们检查一个给定的顶点;我们可以做相反的图形DFS。但对于这个问题，似乎低效这样做对图中的每一个顶点。

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.

有没有更好的办法？

感谢。

推荐答案

使用的Tarjan算法找到强烈该图在时间的连接组件 O（| V | + | E |）。如果你再缩水每个组件到一个节点，你会留下一个向无环图。存在一个顶点从所有其他人可以当且仅当恰好有一个顶点在DAG与度0。这是你要找的顶点到达 - 即所谓的母亲顶点

Use Tarjan'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".

这篇关于图 - 找到顶点从所有其它顶点可达的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！