データ構造とアルゴリズム、グラフをトラバースする2つの方法を理解する

[[331362]]

1 はじめに

トラバーサルとは、特定のノードから開始し、特定の検索ルートに従ってデータ構造内のすべてのノードを順番に訪問し、各ノードを 1 回だけ訪問することを意味します。

バイナリ ツリーの基礎では、ツリー トラバーサルが紹介されます。ツリー トラバーサルとは、ルート ノードから開始し、特定のアクセス ルールに従ってツリーの各ノード情報に順番にアクセスすることを意味します。ツリー トラバーサル プロセスは、さまざまなアクセス ルールに応じて 4 つの主要なトラバーサル モードに分けられます。

（１）事前順序トラバーサル

（２）順序走査

（３）後順序探索

（４）階層的トラバーサル

同様に、グラフ トラバーサルとは、特定のグラフ内の指定された頂点 (初期点と呼ばれる) から開始し、特定の検索方法に従ってグラフのエッジに沿ってグラフ内のすべての頂点を訪問し、各頂点を 1 回だけ訪問することを意味します。このプロセスはグラフ トラバーサルと呼ばれます。トラバーサル処理中に取得される頂点シーケンスは、グラフ トラバーサル シーケンスと呼ばれます。

グラフトラバーサルのプロセスでは、異なる検索方法に応じて2つの検索戦略があります。（1）深さ優先探索（DFS）（2）幅優先探索（BFS）

2 深さ優先探索

2.1 アルゴリズムのアイデア

深さ優先探索の考え方は次のとおりです。初期状態がグラフ内のすべての頂点が訪問されていないと仮定し、頂点 v から始めて、最初に頂点を訪問し、次に深さ優先探索を使用して、v に接続するパスを持つグラフ内のすべての頂点が訪問されるまで、グラフを順番に、訪問されていない各隣接ポイントからトラバースします。この時点でまだ訪問していない頂点が他にもある場合は、別の未訪問の頂点を開始点として選択し、グラフ内のすべての頂点が訪問されるまで上記のプロセスを繰り返します。

2.2 アルゴリズムの特徴

深さ優先探索は再帰的なプロセスです。まず、開始点を選択してそこを移動します。まだ訪問していない隣接ノードがある場合は、前進を続けます。前進できない場合は、一歩後退してから前進してください。一歩後退した後も前進できない場合は、前進できるようになるまで後退し続けます。選択したポイントに接続されているすべての頂点を通過するまで、このプロセスを繰り返します。 深さ優先探索はバックオフ操作を伴う再帰プロセスであるため、アクセス パス情報を格納するためのスタックが必要です。現在訪問している頂点に、前進する隣接頂点がない場合、現在の位置をポップ要素の位置に戻すには、ポップ操作が必要です。

2.3 グラフィカルプロセス

2.3.1 無向グラフ上の深さ優先探索

深さ優先探索のトラバーサルプロセスは、図 2.3.1.1 に示す無向グラフを使用して説明されます。

図2.3.1.1

（１）まず、頂点Aを開始点として選択し、Aの頂点情報を出力し、Aをスタックにプッシュし、Aを訪問済み頂点としてマークします。

（２）Aの隣接頂点はC、D、Fです。いずれか１つを選んで先に進みます。ここでは、頂点 C を前方位置頂点として選択します。 C の頂点情報を出力し、C をスタックにプッシュし、C を訪問済み頂点としてマークします。現在の位置は頂点 C を指しています。

（３）頂点Cの隣接頂点はA、D、Bである。この時点で、Aは訪問済み頂点としてマークされており、それ以上訪問することはできない。前進するには、B または D から頂点を選択します。ここでは、前進位置の頂点として頂点 B を選択します。 B の頂点情報を出力し、B をスタックにプッシュし、頂点 B を訪問済み頂点としてマークします。現在の位置は頂点 B を指しています。

（４）頂点Bの隣接頂点はCとEのみである。Cはマークされており、これ以上アクセスできない。そのため、Eが前方位置頂点として選択され、Eの頂点情報が出力され、Eがスタックにプッシュされ、頂点Eがマークされ、現在の位置はEを指す。

（５）頂点Eの隣接頂点がすべてマークされた。この時点では前進は不可能であり後退する必要がある。現在の位置を頂点 B に戻し、戻りながらスタックから E をポップします。

(6) 頂点Bの隣接頂点もマークされているので、バックトラックを続ける必要があります。現在の位置はCにバックトラックされ、同時にBがスタックからポップアウトされます。

（７）頂点Cが移動できる頂点位置がDである場合、Dの頂点情報を出力し、Dをスタックにプッシュし、頂点Dをマークする。現在の位置は頂点 D を指しています。

（８）頂点Dには前方頂点位置がないのでバックオフ操作が必要である。現在の位置を頂点 C に戻し、同時にスタックから D をポップします。

(9) 頂点Cにはそれ以上進むべき頂点位置がないので、バックトラックを続けて現在の位置を頂点Aに戻し、同時に頂点Cをスタックからポップします。

(10) 頂点Aの頂点位置はFである。Fの頂点情報を出力し、Fをスタックにプッシュし、Fにマークを付けます。現在の位置を頂点 F に設定します。

（１１）頂点Fの前方頂点位置はGである。Gの頂点情報を出力し、Gをスタックにプッシュし、Gにマークを付ける。現在の位置を頂点Gに設定します。

（１２）頂点Gは前方頂点位置を持たず、Fに戻る。現在の位置は F を指しており、戻る際に G がスタックからポップされます。

(13) 頂点Fには前方頂点位置がないので、頂点Aに戻ります。現在の位置はAを指しており、戻る際にFがスタックからポップされます。

(14) 頂点Aには前方頂点位置がないので、バックトラックを続けます。スタックが空になると、Aから始まるトラバーサルは終了します。グラフ内にまだ訪問されていない頂点がある場合は、その訪問されていない頂点を開始点として選択し、このプロセスを続行します。すべての頂点が訪問されるまで。

（15）深さ優先探索の走査順序はA->C->B->E->D->F->Gである。

2.3.2 有向グラフ深さ優先探索

深さ優先探索のトラバーサルプロセスは、図 2.3.2.1 に示す有向グラフを使用して説明されます。

図2.3.2.1 有向グラフ

（１）頂点Aを開始点として、Aを出力し、Aをスタックにプッシュし、Aにマークを付ける。現在の位置は A を指しています。

(2) Aを末尾とする辺は1つだけであり、その辺の先頭は頂点Bである。この場合、前方位置は頂点Bである。Bを出力し、Bをスタックにプッシュし、Bにマークを付ける。現在の位置は B を指しています。

（３）頂点Bが移動できる位置はCとFである。移動先の位置としてFを選択し、Fを出力し、Fをスタックにプッシュし、Fにマークを付ける。現在の位置は F を指しています。

（４）頂点Fの前方位置はGである。Gを出力し、Gをスタックにプッシュし、Gにマークを付ける。現在の位置は G を指しています。

（５）頂点Gにはこれ以上進むべき位置がないので、Fに戻ってスタックからFをポップします。現在の位置は F を指しています。

（6）頂点Fが前進できる位置はもうないので、Bまで後退し続け、Fをスタックからポップします。現在の位置は B を指しています。

（7）頂点Bは位置CとEに移動できます。Eを選択し、Eを出力し、Eをスタックにプッシュし、Eにマークを付けます。現在の位置は E を指しています。

（８）頂点Eの前方位置はDである。Dを出力し、Dをスタックにプッシュし、Dにマークを付ける。現在の位置は D を指しています。

（９）頂点Dの前方位置はCである。Cを出力し、Cをスタックにプッシュし、Cにマークを付ける。現在の位置は C を指しています。

(10) 頂点Cには前方位置がないので、Dに戻り、Cをスタックからポップします。

（11）スタックが空になり、Aから始まるトラバーサルプロセスが終了するまでこのプロセスを続けます。グラフ内にまだ訪問されていない頂点がある場合は、その訪問されていない頂点を開始点として選択し、このプロセスを続行します。すべての頂点が訪問されるまで。

2.4 アルゴリズム分析

グラフが隣接行列を使用して保存される場合、行列要素の数は n^2 なので、時間計算量は O(n^2) になります。 グラフが隣接リストを使用して保存される場合、隣接リストにはエッジ ノード (e 個のエッジ、無向グラフには 2e 個のノードのみ) のみ保存され、ヘッダー ノードは n (つまり、頂点の数) であるため、時間計算量は O(n+e) になります。

3 幅優先探索

3.1 アルゴリズムのアイデア

幅優先探索の考え方は、グラフ内の頂点 v から開始し、v を訪問した後、v のまだ訪問されていない各隣接点を順番に訪問し、次にこれらの隣接点から開始してそれらの隣接点を順番に訪問し、「最初に訪問した頂点の隣接点が、後で訪問した頂点の隣接点よりも先に訪問され、グラフ内の訪問された頂点のすべての隣接点が訪問されるまで」というものです。この時点でまだ訪問されていない頂点がグラフ内に存在する場合は、まだ訪問されていない別の頂点を新しい開始点として選択し、グラフ内のすべての頂点が訪問されるまで上記のプロセスを繰り返す必要があります。

3.2 アルゴリズムの特徴

幅優先探索は、グラフの頂点を近いものから遠いものへと巡回するツリーの階層的トラバーサルに似ています。幅優先探索を実行するときに頂点情報を格納するためのキューが必要です。

3.3 グラフィカルプロセス

3.3.1 無向グラフ上の幅優先探索

たとえば、図 3.3.1.1 に示す無向グラフでは、幅優先探索プロセスが使用されています。

図3.3.1.1

（１）Aを開始点として選択し、Aを出力し、Aをキューに入れ、Aにマークを付け、現在の位置はAを指します。

（２）待ち行列の先頭はAであり、Aは待ち行列から出る。 A の隣接頂点は B と E です。B と E を出力し、B と E をキューに入れて、B と E にマークを付けます。現在の位置は A を指しています。

（３）キューの先頭はBであり、Bはキューから出る。 B の隣接頂点は C と D です。C と D を出力し、C と D をキューに入れて、C と D にマークを付けます。現在の位置は B を指しています。

（４）キューの先頭はEであり、Eはキューから出る。 E の隣接頂点は D と F ですが、D はマークされているため、F を出力し、F をキューに入れて、F をマークします。現在の位置は E を指しています。

（５）キューの先頭はCであり、Cはキューから出る。 C の隣接頂点は B と D ですが、B と D の両方がマークされています。キューに入れられた要素はありませんでした。現在の位置は C を指しています。

（６）キューの先頭はDであり、Dはキューから出る。 D の隣接頂点は B、C、E ですが、B、C、E はすべてマークされており、キューに要素は入力されません。現在の位置は D を指しています。

（７）キューの先頭はFであり、Fはキューから出ます。 F の隣接頂点は G と H です。G と H を出力し、G と H をキューに入れて、G と H にマークを付けます。現在の位置は F を指しています。

（８）待ち行列の先頭はGであり、Gは待ち行列から出る。 G の隣接頂点は F ですが、F はマークされており、キューに要素は入力されていません。現在の位置は G を指しています。

（９）待ち行列の先頭はHであり、Hは待ち行列から出る。 H の隣接頂点は F ですが、F はマークされており、キューに要素は入力されていません。現在の位置は H を指しています。

（１０）キューが空の場合、Aから始まるトラバーサルは終了する。グラフ内にまだ訪問されていない頂点がある場合は、その訪問されていない頂点を開始点として選択し、このプロセスを続行します。すべての頂点が訪問されるまで。

3.3.2 有向グラフ上の幅優先探索

図3.3.2.1に示す有向グラフを例に、幅優先探索を実行します。

.3.2.1

（１）Aを開始点として選択し、Aを出力し、Aをキューに入れて、Aにマークを付ける。

（２）待ち行列の先頭はAであり、Aは待ち行列から出る。 A を末尾とする 2 つの辺があり、対応する先頭はそれぞれ B と C です。この場合、A の隣接頂点は B と C です。 B と C を出力し、B と C をキューに入れて、B と C にマークを付けます。

（３）キューの先頭はBであり、Bはキューから出る。 B の隣接頂点はマークされている C なので、キューに新しい要素は追加されません。

（４）キューの先頭はCであり、Cはキューから出る。 C の隣接頂点は E と F です。 E と F を出力し、E と F をキューに入れて、E と F をマークします。

（５）キューの先頭はEであり、Eはキューから出る。 E の隣接頂点は G と H です。 G と H を出力し、G と H をキューに入れて、G と H をマークします。

（６）キューの先頭はFであり、Fはキューから出る。 F には隣接する頂点がありません。

（７）待ち行列の先頭はGであり、Gは待ち行列から出る。 G には隣接する頂点がありません。

（８）待ち行列の先頭はHであり、Hは待ち行列から出る。 H の隣接頂点は E ですが、E はマークされており、キューに新しい要素は追加されません。

（９）キューが空になり、Aから始まるトラバーサル処理が終了する。グラフ内にまだ訪問されていないDがある場合は、Dを開始点としてトラバーサルが続行される。 D を開始点として選択し、D を出力し、D をキューに入れて、D をマークします。

(10) キューの先頭はDで、Dはキューから外れ、Dの隣接頂点はBで、Bはマークされており、キューに新しい要素は入力されません。

（11）キューは空になり、すべての要素が訪問され、幅優先探索のトラバーサルプロセスは終了します。幅優先探索の出力シーケンスは、A->B->E->C->D->F->G->H です。

3.4 アルゴリズム分析

グラフに V 個の頂点と E 個のエッジがあると仮定します。幅優先探索アルゴリズムは V 個のノードを検索する必要があり、時間消費は O(V) です。検索プロセス中、エッジに応じてキューの長さを増やす必要があるため、ここで O(E) が消費されます。一般に、効率は約 O(V+E) です。

4 結論

グラフのトラバーサルでは、主にこれら 2 つのトラバーサルの考え方が使用されます。深さ優先探索では再帰的な方法を使用し、スタック構造の支援が必要です。幅優先探索では、実装を支援するためにキュー構造を使用する必要があります。トラバーサル プロセスでは、接続されたグラフの場合、グラフの任意の頂点から開始する深さ優先または幅優先のトラバーサルによって、グラフ内のすべての頂点に確実にアクセスできますが、接続されていないグラフの場合、グラフの任意の頂点から開始する深さ優先または幅優先のトラバーサルでは、グラフ内のすべての頂点にアクセスできないことがわかります。