深度優先ナビゲーション(DFS)

3709 ワード
DFS アルゴリズム概念 テキストリンク
この文章は本「これはコードテストです」に基づいて書いたものです.

📌 Depth-First Search(DFS)

  • 深さ優先探索.
  • 図における深さ優先探索アルゴリズム

    • 👉 DFSアルゴリズム


    1.ナビゲーション開始ノードをスタックに挿入し、アクセス処理を行います.
    2.スタックの最上位ノードに未アクセスの隣接ノードがある場合は、スタックに入れてアクセス処理を行います.
    アクセスされていない隣接ノードがない場合は、スタックから最上位ノードを取り出します.
    3.再実行できなくなるまで2回目の手順を繰り返します.

    🧐 例


    ノード1から、DFSを使用して次の図を参照します.

    step1

  • 開始ノード「1」をスタックに挿入し、アクセス処理を行う.

    • step2

  • スタックの最上位ノード「1」でアクセスされていない隣接ノード「2」、「3」、「8」で最も小さいノード「2」をスタックに入れてアクセス処理を行う.

    • step3

  • スタックの最上位ノード「2」でアクセスされていない隣接ノード「7」をスタックに入れてアクセス処理を行う.

    • step 4 ~ step 5

  • 以前の手順と同じです

    • ⭐ step 6

  • スタックの最上位ノード「8」には、アクセスされていない隣接ノードはありません.
    したがって、スタックから「8」番ノードを取り出します.

    • step 7 ~ step 9

  • step 6と同じです.

    • step 10

  • スタックの最上位ノード「1」でアクセスされていない隣接ノード「3」をスタックに入れてアクセス処理を行う.

    • step 11

  • スタックの最上位ノード「3」でアクセスされていない隣接ノード「4」、「5」で最も小さいノード「4」をスタックに入れてアクセス処理を行う.

    • step 12

  • スタックの最上位ノード「4」でアクセスされていない隣接ノード「5」をスタックに入れてアクセス処理を行う.

    • step 13

  • 残りのノードには、アクセスされていない隣接ノードはありません.したがって、すべてのノードスタックから取り出します.

    • 結果


    ノードのナビゲーション順序はスタックに入る順序です.
    ノードのナビゲーション順序は次のとおりです.
    1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5
    はい.

    9000 DFSコード

    def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end='')
    
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[v]:
            dfs(graph, i, visited)
    [react]リストとKey
    HDU 4671 Backup Plan(水題)