[アルゴリズム概念]DFS、深度優先探索、プリアンブル優先探索


DFS (Depth-First Search)


コンセプト

  • 深さ優先ブラウズによるグラフィックの深さの深い部分の優先ブラウズのアルゴリズム

  • スタック
  • 動作
  • 現在のノード
  • へのアクセス
  • は、現在のノードに接続するすべてのノードのうち、アクセスされていないノード
  • にアクセスする.
  • をすべてのノード
  • にアクセスするまで繰り返します.

  • すべてのノードをグラフィックまたはツリーで参照できます.

  • ループアルゴリズム(呼び出し自体)なので、ノードにアクセスするかどうかのリストが必要です
  • DFS Python実施
    def dfs(graph, v, visited):
        visited[v] = True
        print(v, end = ' ')
    
        for i in graph[v]:
            if not visited[i]:
                dfs(graph, i, visited)
    
    graph = [
        [],
        [2,3,8],
        [1,7],
        [1,4,5],
        [3,5],
        [3,4],
        [7],
        [2,6,8],
        [1,7]
    ]
    
    visited = [False] * 9
    
    dfs(graph, 1, visited)
    

    DFS : 1 2 7 6 8 3 4 5

    BFS (Breadth-First Search)


    コンセプト

  • 図面内の最も近いノードを優先的に参照するアルゴリズム

  • キューの使用
  • 動作
  • 現在のノードをキューに挿入するアクセス処理
  • を行う.
  • キューからノードを取り出し、そのノードの隣接ノードのすべての未アクセスノードをキューに挿入してアクセス処理
  • を行う.
  • をすべてのノード
  • にアクセスするまで繰り返します.

  • すべてのノードをグラフィックまたはツリーで参照できます.

  • ループアルゴリズム(呼び出し自体)なので、ノードにアクセスするかどうかのリストが必要です
  • DFS Python実施
    from collections import deque
    
    
    def bfs(graph, start, visited):
    
        queue = deque([start])
    
        visited[start] = True
    
        while queue :
    
            v = queue.popleft()
            print(v, end=' ')
    
            for i in graph[v]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True
    
    
    
    graph = [
        [],
        [2,3,8],
        [1,7],
        [1,4,5],
        [3,5],
        [3,4],
        [7],
        [2,6,8],
        [1,7]
    ]
    
    visited = [False] * 9
    
    bfs(graph, 1, visited)
    
    

    BFS : 1 2 3 8 7 4 5 6
    [ソース:ツリーウィキ]
    https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3