Data-structures-algorithms-depth-first-traversal
提供：Dev Guides
データ構造-深さ優先走査
深さ優先検索（DFS）アルゴリズムは、深さ方向にグラフを走査し、スタックを使用して、繰り返しで行き止まりが発生したときに、検索を開始する次の頂点を取得することを忘れないようにします。
上記の例のように、DFSアルゴリズムは最初にSからA、D、G、E、Bを横断し、次にF、最後にCを横断します。 以下のルールを採用しています。
- *ルール1 *-隣接する未訪問の頂点を訪問します。 訪問済みとしてマークします。 それを表示します。 スタックにプッシュします。
- *ルール2 *-隣接する頂点が見つからない場合、スタックから頂点をポップアップします。 （スタックからすべての頂点がポップアップされますが、隣接する頂点はありません。）
- *ルール3 *-スタックが空になるまでルール1とルール2を繰り返します。
| Step | Traversal | Description |
|---|---|---|
| 1 | Depth First Search Step One | Initialize the stack. |
| 2 | Depth First Search Step Two | Mark S *as visited and put it onto the stack. Explore any unvisited adjacent node from S*. We have three nodes and we can pick any of them. For this example, we shall take the node in an alphabetical order. |
| 3 | Depth First Search Step Three | Mark A *as visited and put it onto the stack. Explore any unvisited adjacent node from A. Both S and D are adjacent to A *but we are concerned for unvisited nodes only. |
| 4 | Depth First Search Step Four | Visit* D and mark it as visited and put onto the stack. Here, we have B and C nodes, which are adjacent to D *and both are unvisited. However, we shall again choose in an alphabetical order. |
| 5 | Depth First Search Step Five | We choose* B*, mark it as visited and put onto the stack. Here B *does not have any unvisited adjacent node. So, we pop B *from the stack. |
| 6 | Depth First Search Step Six | We check the stack top for return to the previous node and check if it has any unvisited nodes. Here, we find* D *to be on the top of the stack. |
| 7 | Depth First Search Step Seven | Only unvisited adjacent node is from* D is C now. So we visit C*, mark it as visited and put it onto the stack. |
*C* には未訪問の隣接ノードがないため、未訪問の隣接ノードを持つノードが見つかるまでスタックをポップし続けます。 この場合、何も存在せず、スタックが空になるまでポップを続けます。Cプログラミング言語でのこのアルゴリズムの実装について知るには、リンク：/data_structures_algorithms/depth_first_traversal_in_c [ここをクリック]をクリックしてください。
