圖 - 找到從所有其他頂點可到達的頂點

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）的時間來解決該問題。