グラフトラバーサル
グラフトラバーサルとは、ウェル内のすべての頂点とエッジに1回だけアクセスすることを意味します。 -定義された順序。特定のグラフアルゴリズムを使用している間は、グラフの各頂点に1回だけアクセスする必要があります。頂点にアクセスする順序は重要であり、解決するアルゴリズムまたは質問によって異なる場合があります。
トラバーサル中は、どの頂点にアクセスしたかを追跡することが重要です。頂点を追跡する最も一般的な方法は、頂点にマークを付けることです。
幅優先探索（BFS）
グラフを走査する方法はたくさんあります。 BFSは最も一般的に使用されるアプローチです。
BFSはトラバースアルゴリズムであり、選択したノード（ソースノードまたは開始ノード）からトラバースを開始し、グラフをレイヤーごとにトラバースして、隣接ノード（ソースノードに直接接続されているノード）を探索する必要があります。次に、次のレベルの隣接ノードに向かって移動する必要があります。
BFSの名前が示すように、次のようにグラフを横方向にトラバースする必要があります。
- 最初に水平に移動し、現在のレイヤーのすべてのノードにアクセスします
- 次のレイヤーに移動します
次の図を検討してください。
レイヤー1のノード間の距離は、レイヤー2のノード間の距離よりも比較的小さいため、BFSでは、レイヤー2のノードに移動する前に、レイヤー1のすべてのノードをトラバースする必要があります。
子ノードのトラバース
グラフにはサイクルを含めることができます。これにより、グラフをトラバースしているときに同じノードに再び移動する場合があります。同じノードが再度処理されないようにするには、処理後にノードをマークするブール配列を使用します。グラフのレイヤー内のノードにアクセスするときは、対応する子ノードを同様の順序でトラバースできるようにノードを格納します。
このプロセスを簡単にするには、キューを使用してノードを保存し、すべての隣接ノード（ノードに直接接続されている頂点）がマークされるまで、ノードを「訪問済み」としてマークします。キューは先入れ先出し（FIFO）キューイング方式に従うため、ノードのネイバーはノードに挿入された順序でアクセスされます。つまり、最初に挿入されたノードが最初にアクセスされます。オン。
擬似コード
トラバースプロセス
トラバースソースノードから開始し、sをキューにプッシュします。 sは「訪問済み」としてマークされます。
最初の反復
- はキューからポップされます
- sの隣人、つまり1と2がトラバースされます
- 以前にトラバースされていない1と2がトラバースされます。
- キューにプッシュされます
- 1と2は訪問済みとしてマークされます
2回目の反復
- 1がキューからポップされます
- 1のネイバー、つまりsと3がトラバースされます
- sは「訪問済み」としてマークされているため、無視されます
- 3は以前にトラバースされていませんがトラバースされます。
- キューにプッシュされました
- 訪問済みとしてマークされました
3回目の反復
- 2がキューからポップされます
- 2のネイバー、つまりs、3、および4がトラバースされます
- 3およびsは、「訪問済み」としてマークされているため無視されます
- 4は、以前にトラバースされていませんが、トラバースされます。
- キューにプッシュされました
- 訪問済みとしてマークされました
4回目の反復
- 3がキューからポップされます
- 3のネイバー、つまり1、2、および5がトラバースされます
- 1および2は、「訪問済み」としてマークされているため無視されます
- 5は、以前にトラバースされていませんが、トラバースされます。
- キューにプッシュされました
- 訪問済みとしてマークされました
5回目の反復
- 4はキューからポップされます
- 4のネイバー、つまり2がトラバースされます
- 2はすでに「訪問済み」としてマークされているため、無視されます
6回目の反復
- 5がキューからポップされます
- 5のネイバー、つまり3がトラバースされます
- 3は無視されます。すでに「訪問済み」としてマークされています
キューは空であり、ループから抜け出します。すべてのノードはBFSを使用してトラバースされています。
グラフ内のすべてのエッジが同じ重みである場合、BFSを使用してグラフ内のノード間の最小距離を見つけることもできます。
例
この図のように、ソースノードから開始して、ソース間の距離を見つけますノードとノード1。BFSアルゴリズムに従わない場合は、ソースノードからノード2、次にノード1に移動できます。このアプローチでは、ソースノードとノード1の間の距離が2として計算されますが、最小値は距離は実際には1です。最小距離は、BFSアルゴリズムを使用して正しく計算できます。
複雑さ
BFSの時間計算量はO（V + E）です。ここで、Vはノードの数、Eはエッジの数です。
アプリケーション
1。特定のツリーの各ノードのレベルを決定する方法は？
BFSで知っているように、レベルごとにトラバースします。 BFSを使用して、各ノードのレベルを決定することもできます。
実装
このコードはBFSコードに似ていますが、次の違いがあります。
level] = level + 1;
このコードでは、各ノードにアクセスしている間、そのノードのレベルは、その親ノードのレベルの増分で設定されます。これが各ノードのレベルの決定方法です。
2 。 0-1 BFS
このタイプのBFSは、グラフのエッジの重みが0または1の場合に、グラフ内の2つのノード間の最短距離を見つけるために使用されます。前に説明したBFSを適用する場合この記事では、2つのノード間の最適な距離に対して誤った結果が得られます。
このアプローチでは、最適な距離の条件がチェックされるため、ノードをマークするためにブール配列は使用されません。各ノードにアクセスします。両端キューは、ノードを格納するために使用されます。 0-1 BFSでは、エッジの重みが0の場合、ノードはデキューの先頭にプッシュされます。エッジの重みが1の場合、ノードはデキューの後ろにプッシュされます。
実装
Qは両端キューです。 distanceは配列であり、distanceには開始ノードからvノードまでの距離が含まれます。最初、ソースノードから各ノードまでに定義された距離は無限大です。
次のグラフでこのコードを理解しましょう：
グラフの隣接リストは次のようになります。
ここで、「s」は0またはソースノードと見なされます。
0- > 1- > 3- > 2
Edges.first = 1、edges.second = 1
edges.first = 3、edges.second = 0
Edges.first = 2、edges.second = 1
1 -> 0- > 4
edges.first = 0、edges.second = 1
Edges.first = 4 、edges.second = 0
2- > 0- > 3
Edges.first = 0 、edges.second = 0
Edges.first = 3、edges.second = 0
3- > 0- > 2- > 4
edges.first = 0、edges.second = 0
Edges.first = 2、edges.second = 0
Edges.first = 4、edges.second = 0
4- > 1- > 3
Edges.first = 1、edges.second = 0
Edges.first = 3、edges.second = 0
BFSアルゴリズムを使用すると、結果が不正確になります。 s間の最適な距離ノード1とsおよびノード2をそれぞれ1として。これは、sの子を訪問し、sとその子の間の距離（1）を計算するためです。実際の最適距離はどちらの場合も0です。
処理
ソースノード、つまり0から開始して、1、2、および3に向かって移動します。0と1の間および0と2の間のエッジの重みはそれぞれ1であるため、1および2はキューの最後にプッシュされます。ただし、0と3の間のエッジの重みは0であるため、3はキューの先頭にプッシュされます。距離はそれに応じて距離配列で維持されます。
3がキューからポップされ、同じプロセスが隣接するものに適用されます。