14

私は、問題の1つが、有向グラフG =（V、E）が単一に接続されているかどうかを確認するアルゴリズムを導出するように要求する割り当てに取り組んでいます（すべての異なる頂点uに対してuからvへの単純なパスが最大で1つあります。 Vのv。

もちろん、ブルートフォースチェックを行うこともできます。これは私が現在行っていることですが、もっと効率的な方法があるかどうかを知りたいと思います。誰かが私を正しい方向に向けることができますか？

4

7 に答える 7

5

この質問には、より良い答えがあります。O（| V | ^ 2）でそれを行うことができます。さらに努力すれば、線形時間でそれを行うことができます。

最初に、G の強連結成分を見つけます。各強成分で、次のケースを見つけるために検索します: 1) この成分に前方エッジがある場合、それは単一連結ではありません。2) この成分にクロス エッジがある場合。 3) 頂点 u をルートとするツリーに、u の適切な祖先に少なくとも 2 つのバック エッジがある場合、それは単独で接続されていません。

これは O(E) で実行できます。(ケース3以外だと思います。うまく実装できませんでした!!)。

上記のケースのいずれも発生しなかった場合は、バックエッジがないため、G^SCC にクロス エッジまたはフォワード エッジがあるかどうかを確認する必要があります (グラフ G、単一のノードに置き換えられた強力なコンポーネント)。 O(|V|^2) 内のこのグラフの各頂点で dfs を繰り返します。

于 2010-06-05T05:53:21.170 に答える
4

DFSを試しましたか。

Run DFS for every vertex in the graph as source
    If a visited vertex is encountered again, the graph is not singly connected
repeat for every unvisited vertex.
The graph is singly connected.

複雑さ O(v^2), o(v) dfs 繰り返しなし。

于 2010-03-24T21:01:00.670 に答える
3

これを読んでください。本当によく説明しています。

于 2014-01-05T08:02:51.097 に答える
0

その複雑さが O(V^2) になることに同意しません。DFS では、アルゴリズムの概要の本のようにすべての頂点に対してそれを呼び出すわけではないため、構文は DFS(G) です。BFS とは異なり、単一の頂点ではなく、グラフ全体に対してのみ DFS を呼び出します。したがって、この場合、私によると、DFS を 1 回呼び出して確認する必要があります。訪問した頂点が再び検出された場合、グラフは単独で接続されていません (切断されたコンポーネントごとに呼び出す必要がありますが、既にコードに含まれています)。 ）。SO 複雑さは O(V+E) になります。ここでは E=V であるため、複雑さは O(V) である必要があります。

于 2013-06-30T13:11:21.750 に答える
0

私はこれについて考えました: 1) 任意の頂点から DFS を実行します。すべての頂点が前方エッジなしで DFS でカバーされている場合 (そうでなければ、すべての頂点がカバーされないため、交差することはありません)、潜在的な候補になる可能性があります。

2) DFS で見つかった頂点 (レベル j) にレベル i へのバック エッジがある場合、それ以降に見つかった他の頂点は、j 未満のレベルの頂点に向かってバック エッジを持つべきではなく、すべての頂点がroot (2 番目の DFS で確認)。

これが正しければ、これは線形時間で行われます。

于 2013-11-09T20:36:33.593 に答える
-1

各頂点から DFS を 1 回実行します。コンポーネント内に前方エッジがなく、クロス エッジがない場合にのみ、グラフは単結合です。

複雑度 : O(VE)

于 2011-05-18T23:48:28.080 に答える