Data-structures-algorithms-breadth-first-traversal

データ構造-幅優先走査

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

幅優先トラバーサル

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

• *ルール1 *-隣接する未訪問の頂点を訪問します。 訪問済みとしてマークします。 それを表示します。 キューに挿入します。
• *ルール2 *-隣接する頂点が見つからない場合、キューから最初の頂点を削除します。
• *ルール3 *-キューが空になるまでルール1とルール2を繰り返します。

Step	Traversal	Description
1	Breadth First Search Step One	Initialize the queue.
2	Breadth First Search Step Two	We start from visiting *S *(starting node), and mark it as visited.
3	Breadth First Search Step Three	We then see an unvisited adjacent node from* S*. In this example, we have three nodes but alphabetically we choose A, mark it as visited and enqueue it.
4	Breadth First Search Step Four	Next, the unvisited adjacent node from S *is B*. We mark it as visited and enqueue it.
5	Breadth First Search Step Five	Next, the unvisited adjacent node from S *is C*. We mark it as visited and enqueue it.
6	Breadth First Search Step Six	Now, S *is left with no unvisited adjacent nodes. So, we dequeue and find A*.
7	Breadth First Search Step Seven	From A *we have D* as unvisited adjacent node. We mark it as visited and enqueue it.

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

Cプログラミング言語でのこのアルゴリズムの実装は、リンクすることができます：/data_structures_algorithms/breadth_first_traversal_in_c [ここに表示]。