[알고리즘] BFS(너비 우선 탐색) 정리

[알고리즘] BFS(너비 우선 탐색) 정리

아래와 같이 그래프가 있을 때 BFS 구현 방법에 대해 작성한다.

• 그래프

  graph = [
      [],
      [2,3,8], # [1]번 노드와 연결된 노드: 2, 3, 8번 노드
      [1,7], # [2]번 노드와 연결된 노드: 1, 7번 노드
      [1,4,5],
      [3,5],
      [3,4],
      [7],
      [2,6,8],
      [1,7]
  ]

• BFS for graph

  • 큐를 사용하는 BFS - deque사용

    from collections import deque
    
    # BFS 메서드 정의
    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
    
    visited = [False] * 9
    bfs(graph, 1, visited)

  • 출력

    1 2 3 8 7 4 5 6