グラフ - 他のすべての頂点から到達可能な頂点を見つけよう

Question

グラフがあれば、他のすべての頂点に到達可能な頂点vが存在するかどうかをどのように判断できますか？アルゴリズムは可能な限り効率的でなければならない。

与えられた頂点をチェックしている場合、私はそれを行う方法を知っています。逆のグラフでdfsを行うことができます。しかし、この質問のためには、グラフ内のすべての頂点に対して行うのは非効率的です。

良い方法がありますか？

ありがとうございました。

Answer 1

を使用すると、グラフの強連結成分を時刻O(|V|+|E|)に見つけることができます。各コンポーネントを1つのノードに「縮小」すると、有向非循環グラフが残されます。 DAGにin-degree 0の厳密に1つの頂点がある場合に限り、他のすべての頂点に到達できる頂点が存在します。これは、探している頂点、いわゆる「母頂点」です。

注：この回答は、もともとTarjanのアルゴリズムを使用することをお勧めします。 Tarjanの方が少し早いかもしれませんが、Kosarajuよりも少し複雑です。

Answer 2

私はちょうど次のアルゴリズムを発明しました。

• 任意の頂点から開始し、「visited」としてマークします。
• グラフ内の任意の親頂点に移動し、 'visited'としてマークします。
• スタック上の訪問頂点を追跡します。
• 親の頂点がない頂点に達した場合は、それが他のすべての頂点に到達可能な頂点かどうかを確認します。
• 既に訪問した頂点Vに到達したとき：
  1. 訪問先の頂点Vをスタックに追加しないでください。前の頂点を、強く接続されたコンポーネントの「終わり」としてマークします。
  2. 既に訪問した頂点Vに達するまでスタックを下に移動します。 途中で、「終了」と「開始」のすべてのマーキングを削除します。 最後のマーキングが削除された場合は、Vを '開始'とマークし、それ以外の場合はマークしないでください。
  3. もう一度スタックの一番上から開始し、未訪問の親を持つ頂点を見つけるまで（そしてアルゴリズムの最初のステップに進みます）、または「開始」とマークされた頂点に達するまで下に移動し、確かに他のすべてのものが到達可能な母の頂点です。

アイデアはどの頂点が母親の頂点から到達可能でなければなりませんので、我々は高い行くことができないまで、私たちは、上向きの任意のパスを取ることができ、ということです。

このようにして、開始頂点に到達できる強固に接続されたコンポーネントのみをチェックします。 in-degree 0の強く接続されたコンポーネントがたくさんある場合、これはAndyのアルゴリズムよりも明らかに有利です。

Answer 3

解決策は、強固に接続されたコンポーネントのコサラジュのアルゴリズムの概念を使用して見つけることができます。この考えは、次の事実に基づいています。

他のすべての頂点に到達可能な頂点（または頂点）が存在する場合、この頂点はDFSトラバーサルで最大終了時間を持ちます。 ようなので、解決策はなります。上記のアルゴリズムは、問題を解決するためのO（V + E）の時間を要する

// 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); 
} 

。