6

非接続グラフの接続コンポーネントを決定するために、BFS または DFSアルゴリズムを使用してアルゴリズムを設計するにはどうすればよいですか。アルゴリズムは、各接続コンポーネントの頂点のセットを示すことができなければなりません。

これは私のアプローチです：

1) すべての頂点を未訪問として初期化します。

2) 任意の頂点 v から始まるグラフの DFS トラバーサルを実行します。DFS トラバーサルがすべての頂点を訪問しない場合は、false を返します。

3) すべての円弧を逆にする (またはグラフの転置または反転を見つける)

4) 逆グラフですべての頂点を未訪問としてマークします。

5) 同じ頂点 v から始まる逆グラフの DFS トラバーサルを実行します (ステップ 2 と同じ)。DFS トラバーサルがすべての頂点を訪問しない場合は、false を返します。それ以外の場合は true を返します。

アイデアは、すべてのノードが頂点 v から到達でき、すべてのノードが v に到達できる場合、グラフは強く接続されているということです。ステップ 2 では、すべての頂点が v から到達可能かどうかを確認します。ステップ 4 では、すべての頂点が v に到達できるかどうかを確認します (逆グラフでは、すべての頂点が v から到達可能であれば、すべての頂点が元のグラフの v に到達できます)。

このソリューションを改善する方法について何か考えはありますか?

4

4 に答える 4

3

どうですか

  • let vertices= 入力
  • let results= 空のリスト
  • に頂点がある間vertices:
    • セットを作成するS
    • 任意の未探索の頂点を選び、 に入れますS。
    • その頂点から BFS/DFS を実行し、各頂点が見つかったら、それを から削除してverticesに追加しSます。
    • Sに追加results
  • 戻るresults

これが完了すると、頂点のセットのリストが得られます。各セットは、いくつかの頂点から検索するグラフから作成されました (各セットの頂点を接続します)。無向グラフを想定すると、これは問題なく動作するはずです (頭の中で)。

于 2013-11-01T23:16:11.550 に答える
0

この問題を解決する標準的な方法は、各ノードから開始して DFS を実行することです。

すべてのノードを未訪問としてラベル付けすることから始めます。次に、任意の順序でノードを反復処理します。ノードごとに、接続されたコンポーネントにあるというラベルがまだ付けられていない場合は、そのノードから DFS を実行し、到達可能なすべてのノードを同じ CC にあるものとしてマークします。ノードがすでにマークされている場合は、スキップします。次に、グラフのすべての CC を 1 つの CC ずつ検出します。

さらに、これは非常に効率的です。m 個のエッジと n 個のノードがある場合、各ノードとエッジは最大 2 回訪問されるため、実行時間は最初のステップ (すべてのノードを未訪問としてマーク) で O(n)、2 番目のステップで O(m + n) になります。したがって、全体の実行時間は O(m + n) です。

お役に立てれば！

于 2013-11-01T23:42:46.207 に答える
0

有向グラフで作業しているようで、連結成分 (強く連結されていない) を見つけたいので、最初にグラフを無向グラフに変換する必要があります。したがって、頂点ごとに、一時的な頂点を反対方向に追加します。次に、まだアクセスされていない各頂点から始まる単純な DFS を使用して、接続されたコンポーネントを見つけることができます。最後に、一時的な頂点を削除できます。

于 2013-11-02T01:16:53.280 に答える