グラフがあれば、他のすべての頂点に到達可能な頂点vが存在するかどうかをどのように判断できますか?アルゴリズムは可能な限り効率的でなければならない。グラフ - 他のすべての頂点から到達可能な頂点を見つけよう
与えられた頂点をチェックしている場合、私はそれを行う方法を知っています。逆のグラフでdfsを行うことができます。しかし、この質問のためには、グラフ内のすべての頂点に対して行うのは非効率的です。
良い方法がありますか?
ありがとうございました。
グラフがあれば、他のすべての頂点に到達可能な頂点vが存在するかどうかをどのように判断できますか?アルゴリズムは可能な限り効率的でなければならない。グラフ - 他のすべての頂点から到達可能な頂点を見つけよう
与えられた頂点をチェックしている場合、私はそれを行う方法を知っています。逆のグラフでdfsを行うことができます。しかし、この質問のためには、グラフ内のすべての頂点に対して行うのは非効率的です。
良い方法がありますか?
ありがとうございました。
を使用すると、グラフの強連結成分を時刻O(|V|+|E|)
に見つけることができます。各コンポーネントを1つのノードに「縮小」すると、有向非循環グラフが残されます。 DAGにin-degree 0の厳密に1つの頂点がある場合に限り、他のすべての頂点に到達できる頂点が存在します。これは、探している頂点、いわゆる「母頂点」です。
注:この回答は、もともとTarjanのアルゴリズムを使用することをお勧めします。 Tarjanの方が少し早いかもしれませんが、Kosarajuよりも少し複雑です。
私はちょうど次のアルゴリズムを発明しました。
アイデアはどの頂点が母親の頂点から到達可能でなければなりませんので、我々は高い行くことができないまで、私たちは、上向きの任意のパスを取ることができ、ということです。
このようにして、開始頂点に到達できる強固に接続されたコンポーネントのみをチェックします。 in-degree 0の強く接続されたコンポーネントがたくさんある場合、これはAndyのアルゴリズムよりも明らかに有利です。
解決策は、強固に接続されたコンポーネントのコサラジュのアルゴリズムの概念を使用して見つけることができます。この考えは、次の事実に基づいています。
他のすべての頂点に到達可能な頂点(または頂点)が存在する場合、この頂点は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);
}
。
密度の高いグラフでは、Floyd-Warshallを実行して、すべての行を探します。 – dasblinkenlight
この質問は役に立ちますか? http://math.stackexchange.com/questions/99237 –
@Jakeは、他のすべての頂点(タイトルに含意)または他のすべての頂点に到達できる頂点から到達できる頂点を求めるポストです記事自体のように)? – bytefire