图 - 查找从所有其他顶点可到达的顶点

Question

给定一个图形,我们如何确定是否存在顶点v,所有其他顶点都可以从该顶点v到达.算法应该尽可能高效.

如果我们检查一个给定的顶点,我知道怎么做; 我们可以在反向图上做dfs.但是对于这个问题,对图中的每个顶点执行它似乎效率低下.

有没有更好的办法 ？

谢谢.

Answer 1

使用Kosaraju的算法及时找到图中强关联的组件O(|V|+|E|).如果然后将每个组件"缩小"到单个节点,则会留下有向非循环图.存在一个顶点,当且仅当DAG中有一个具有in-degree 0的顶点时,才能到达所有其他顶点.这是您正在寻找的顶点 - 所谓的"母顶点".

注意:这个答案最初建议使用Tarjan的算法.Tarjan的速度可能会快一点,但它也比Kosaraju的复杂一点.

Answer 2

可以通过从 Kosaraju 的强连通分量算法中获取概念来找到解决方案。这个想法基于以下事实：

如果存在一个顶点（或多个顶点），从中可以到达所有其他顶点，则该顶点将在 DFS 遍历中具有最大完成时间。因此，解决方案如下所示：

// Utility function to find mother vertex 
//(vertex from which all other vertices are reachable)

public void findMotherVertex() {
    int motherVertex=0;

    for (int i=0;i<G.V();i++) {  //G.V() would return the no. of vertices in the graph
        if (!marked[i]) {  //marked - boolean array storing visited vertices
            dfs(i);
            motherVertex=i;
        }
    }

    //Check for this vertex if all other vertices have been already visited
    //Otherwise no mother vertex exists

    for (int i=0;i<G.V();i++) {
        if (!marked[i])
            return false;
    }

    System.out.println("Desired vertex is : " + motherVertex);
}

上述算法需要 O(V+E) 时间来解决问题。