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

Question

给定一个图，我们如何确定是否存在顶点v，从中可以找到所有其他顶点。该算法应尽可能高效。

我知道如何做到这一点，如果我们检查给定的顶点;我们可以在反向图上做dfs。但是对于这个问题，对图中的每个顶点执行它似乎效率不高。

有没有更好的方法？

谢谢。

Answer 1

使用Kosaraju's algorithm在时间O(|V|+|E|)中查找图的强连通组件。如果您随后将每个组件“缩小”到单个节点，则会留下一个有向非循环图。存在一个顶点，当且仅当在DAG中只有一个顶点具有入度0时，所有其他顶点才能被达到。这是您要查找的顶点 - 所谓的“母顶点”。

注意：这个答案最初是使用Tarjan算法推荐的。 Tarjan's可能会更快一点，但它也比Kosaraju更复杂一些。

Answer 2

我刚发明了下面的算法。

• 以任意顶点开始并将其标记为'visited'。
• 在图中转到'任意父顶点'并将其标记为'visited'。
• 跟踪堆栈中已访问的顶点。
• 如果您到达没有父顶点的顶点，请检查它是否确实是所有其他顶点都可以到达的顶点。
• 当到达已经访问过的顶点V时：
  1. 不要将访问过的顶点V添加到堆栈。将前一个顶点标记为强连通组件的“结束”。
  2. 沿着堆栈走，直到到达已经访问过的顶点V. 一路走来，你删除所有'结束'和'开始'标记。 如果删除的最后一个标记是“开始”标记，则将V标记为“开始”，否则不要标记。
  3. 再次从堆栈顶部开始往下走，直到找到一个带有未访问父级的顶点（并继续执行算法的第一步），或者直到到达标记为'start'的顶点并检查它是否为确实是所有其他人都可以到达的母顶点。

的想法是，因为任何顶点应该能透过母体的顶点，我们就可以采取任意路径向上，直到我们不能继续走高。

这样我们只检查可以到达起始顶点的强连通组件。在0度内有很多强连通元件的情况下，这将比Andy的算法明显更有优势。

Answer 3

该解决方案可以通过采用Kosaraju的Strongly Connected Components算法的概念来找到。这个想法是基于以下事实：

如果存在一个顶点（或多个顶点），其中所有其他顶点都可以到达，那么这个顶点在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）的时间来解决该问题。