DFS/BFS


DFS(Depth-First Search)
深さ優先探索は深さ優先探索とも呼ばれ、スタックデータ構造(または再帰関数)を利用したグラフィックで深さを優先的に探索するアルゴリズムである.
  • 具体的な動作過程
    1)ナビゲーション開始ノードをスタックに挿入し、アクセスを処理する
    2)隣接ノードがスタックの最上位ノードにアクセスしていない場合、そのノードをスタックに入れてアクセス処理を行う.アクセスされていない隣接ノードがない場合は、スタックから最上位ノードを取り出します.
    3)完了できないまで2回の処理を繰り返す.
  • 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]    
    ]
    
    #각 노드가 방문된 정보를 표현
    #이 때, 0번째 노드도 false로 표현해주기 위해 총 갯수인 9를 곱해준다. 
    visited = [False] * 9 
    
    #정의된 dfs 함수 호출
    dfs(graph, 1, visited)
    BFS(Breadth-First Search)
    幅優先探索は,グラフィックに近いノード優先探索アルゴリズムとも呼ばれ,キューデータ構造を利用する.
    👉 特定の条件の最短パス問題としてもよく用いられる.
  • 具体的な動作過程
    1)ナビゲーション開始ノードをキューに挿入してアクセス処理を行う.
    2)キューからノードを取り出した後,そのノードのすべての隣接ノードにおいてアクセスされていないノードをキューに挿入してアクセス処理を行う.
    3)完了できないまで2回の処理を繰り返す.
  • from collections import deque
    
    #bfs 메서드 정의
    def bfs(graph, start, visited):
        #큐 구현을 위해 deque 라이브러리 사용
        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
    
    #정의된 dfs 함수 호출
    bfs(graph, 1, visited)
    
    <クリーンアップ>

    出典:これが就業コードテストリンクテキスト