グラフィックナビゲーションの基本、DFS、BFS


DFS(Depth-First Search)

  • DFSは、優先的に深度ナビゲーションを行う.図中で深部を優先的にブラウズするアルゴリズム
  • スタックデータ構造(または再帰関数)
  • を使用
    スタックに
  • ナビゲーション開始ノードを挿入し、
  • アクセスを処理する
  • スタック内の隣接ノードがアクセスしていない場合、アクセス処理のためにスタックに格納されます.アクセスされていない隣接ノードがない場合は、スタックから最上位ノードを取り出します.
  • は、2番目のプロセスが再実行できなくなるまで、
  • を繰り返します.
    # DFS 메서드 정의
    def dfs(graph, v, visited):
        # 현재 노드를 방문 처리
        visited[v] = True
        print(v, end=' ')
        # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for i in graph[v]:
            if not visited[i]:
                dfs(graph, i, visited)
    
    # 각 노드가 연결된 정보를 표현 (2차원 리스트)
    graph = [
             [],
             [2,3,8],
             [1,7],
             [1,4,5],
             [3,5],
             [3,4],
             [7],
        [2,6,8],
        [1,7]
    ]
    
    # 각 노드가 방문된 정보를 표현 (1차원 리스트)
    visited = [False] * 9
    
    # 정의된 DFS 함수 호출
    dfs(graph, 1, visited)

    BFS(Breadth-First Search)


    まず
  • 幅を参照します.図面に近いノードから優先ナビゲーション
  • を開始する.
  • キューデータ構造
  • ナビゲーション開始ノードをキューに挿入し、
  • アクセスを処理する
  • キューからノードを取り出し、そのノードのすべての隣接ノードのアクセスされていないノードをキューに挿入し、
  • アクセスを処理する
  • は、2番目のプロセスが再実行できなくなるまで、
  • を繰り返します.
    from collections import deque
    
    # BFS 메서드 정의
    def bfs(graph, start, visited):
        # 큐(Queue) 구현을 위해 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
    
    # 각 노드가 연결된 정보를 표현 (2차원 리스트)
    graph = [
             [],
             [2,3,8],
             [1,7],
             [1,4,5],
             [3,5],
             [3,4],
             [7],
        [2,6,8],
        [1,7]
    ]
    
    # 각 노드가 방문된 정보를 표현 (1차원 리스트)
    visited = [False] * 9
    
    # 정의된 DFS 함수 호출
    bfs(graph, 1, visited)