データ構造-幅優先探索

幅優先探索（BFS）アルゴリズムは、グラフを横方向に移動し、キューを使用して、反復で行き止まりが発生したときに、次の頂点を取得して検索を開始することを忘れないようにします。

上記の例のように、BFSアルゴリズムは、最初にAからB、E、F、次にC、G、最後にDに移動します。次のルールを採用しています。

• Rule 1−隣接する未訪問の頂点にアクセスします。訪問済みとしてマークします。表示します。キューに挿入します。

• Rule 2 −隣接する頂点が見つからない場合は、最初の頂点をキューから削除します。

• Rule 3 −キューが空になるまで、ルール1とルール2を繰り返します。

ステップ	トラバーサル	説明
1		キューを初期化します。
2		私たちは訪問から始めます S （開始ノード）、訪問済みとしてマークします。
3		次に、訪問されていない隣接ノードが S。この例では、3つのノードがありますが、アルファベット順に選択しますA、訪問済みとしてマークし、キューに入れます。
4		次に、からの未訪問の隣接ノード S です B。訪問済みとしてマークし、キューに入れます。
5		次に、からの未訪問の隣接ノード S です C。訪問済みとしてマークし、キューに入れます。
6		さて、 S未訪問の隣接ノードはありません。だから、私たちはデキューして見つけますA。
7		から A 我々は持っています D未訪問の隣接ノードとして。訪問済みとしてマークし、キューに入れます。

この段階では、マークされていない（訪問されていない）ノードはありません。しかし、アルゴリズムに従って、すべての未訪問ノードを取得するためにデキューを続けます。キューが空になると、プログラムは終了します。

Cプログラミング言語でのこのアルゴリズムの実装はここで見ることができます。