幅優先検索 (BFS)

グラフの幅優先検索では、レベルごとに頂点を訪問します。最初のレベルは開始頂点で構成されます。次の各レベルは、前のレベルの頂点に隣接する頂点で構成されます。グラフの幅優先走査は、ツリー走査で説明したツリーの幅優先走査に似ています。ツリーの幅優先走査では、ノードはレベルごとにアクセスされます。最初にルートがアクセスされ、次にルートのすべての子がアクセスされ、次にルートの孫がアクセスされます。同様に、グラフの幅優先検索では、最初に頂点を訪問し、次にその頂点に隣接するすべての頂点を訪問し、次にそれらの頂点に隣接するすべての頂点を訪問する、というように続きます。各頂点が 1 回だけ訪問されるようにするため、すでに訪問されている頂点はスキップされます。

幅優先検索アルゴリズム

グラフの頂点 v から開始する幅優先検索のアルゴリズムは、以下のコードで説明されています。

入力: G = (V, E) および開始頂点 v
出力: v
をルートとする BFS ツリー 1 ツリー bfs(頂点 v) {
2 訪問する頂点を格納するための空のキューを作成します。
3 v をキューに追加します;
4 マーク V を訪問しました;
5
6 while (キューは空ではありません) {
7 頂点、たとえば u をキューからデキューします。
8 通過した頂点のリストに u を追加します;
あなたたちの隣人ごとに9
w がまだ訪問されていない場合は 10 {
11 w をキューに追加します;
12 u をツリー内の w の親として設定します;
13 マークを訪問しました;
14 }
15 }
16 }

下図(a)のグラフを考えてみましょう。頂点 0 から幅優先検索を開始するとします。下の図 (b) に示すように、最初に 0 を訪問し、次にその隣接する頂点 1、2、および 3 をすべて訪問します。頂点 1 には、0、2、および 4 という 3 つの近傍があります。0 と 2 はすでに訪問されているため、次の図 (c) に示すように、ここでは 4 だけを訪問します。頂点 2 には 3 つの近傍、0、1、および 3 があり、これらはすべて訪問済みです。頂点 3 には 3 つの近傍、0、2、および 4 があり、これらはすべて訪問されています。頂点 4 には 2 つの隣接ノード 1 と 3 があり、これらはすべて訪問済みです。したがって、検索は終了します。

各エッジと各頂点は 1 回だけ訪問されるため、bfsメソッドの時間計算量はO(|E| + |V|)です。ここで、|E|はエッジの数を示し、|V を示します|頂点の数。

幅優先検索の実装

bfs(int v)メソッドはGraphインターフェースで定義され、AbstractGraph.java クラスに実装されます (行 197 ～ 222)。頂点 v をルートとするTreeクラスのインスタンスを返します。このメソッドは、検索された頂点をリストsearchOrder(198 行) に保存し、各頂点の親を配列parent(199 行) に保存し、キューのリンク リストを使用します (203 ～ 204 行)。頂点が訪問されたかどうかを示すisVisited配列 (行 207)。検索は頂点vから始まります。vは 206 行目でキューに追加され、訪問済みとしてマークされます (207 行目)。このメソッドはキュー内の各頂点uを検査し (210 行目)、それをsearchOrderに追加します (211 行目)。このメソッドは、uの未訪問の各近隣e.vをキューに追加し(214行目)、その親をuに設定し(215行目)、訪問済みとしてマークします(216行目)。

以下のコードは、シカゴから始まる上図のグラフの BFS を表示するテスト プログラムを提供します。

リーリー

12 個の頂点は次の順序で検索されます:

シカゴ シアトル デンバー カンザスシティ ボストン ニューヨーク
サンフランシスコ ロサンゼルス アトランタ ダラス マイアミ ヒューストン
シアトルの親はシカゴ
サンフランシスコの親はシアトル
ロサンゼルスの親はデンバーです
デンバーの親はシカゴです
カンザスシティの親はシカゴです
ボストンの親はシカゴ
ニューヨークの親はシカゴ
アトランタの親はカンザスシティ
マイアミの親はアトランタです
ダラスの親はカンザスシティ
ヒューストンの親はアトランタです

BFS のアプリケーション

DFS によって解決される問題の多くは、BFS を使用しても解決できます。具体的には、BFS を使用して次の問題を解決できます:

• Mengesan sama ada graf disambungkan. Graf disambungkan jika terdapat laluan antara mana-mana dua bucu dalam graf.
• Mengesan sama ada terdapat laluan antara dua bucu.
• Mencari jalan terpendek antara dua bucu. Anda boleh membuktikan bahawa laluan antara akar dan mana-mana nod dalam pepohon BFS ialah laluan terpendek antara akar dan nod.
• Mencari semua komponen yang bersambung. Komponen bersambung ialah subgraf bersambung maksimum yang mana setiap pasangan bucu disambungkan oleh laluan.
• Mengesan sama ada terdapat kitaran dalam graf.
• Mencari kitaran dalam graf.
• Menguji sama ada graf adalah dwipartit. (Graf adalah dwipartit jika bucu graf boleh dibahagikan kepada dua set bercapah supaya tiada tepi wujud antara bucu dalam set yang sama.)

以上が幅優先検索 (BFS)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。