[PYTHON 알고리즘] # 너비 우선 탐색 (BFS, Breadth-First Search)

그래프 탐색이란

• 하나의 정점으로부터 시작하여 모든 정점들을 한 번씩 방문하는 것이다.

너비 우선 탐색 (BFS, Breadth-First Search)

너비 우선 탐색이란

• 시작 정점으로부터 가까운 정점을 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법은 선택한다.

너비 우선 탐색의 과정

너비 우선 탐색의 특징

• 시작 노드에서 시작하여 거리에 따라 노드의 깊이 별로 탐색하여 직관적이지 않은 면이 있다.
• 재귀적으로 동작하지 않는다.
• 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.
  (이를 하지 않을 경우 무한 루프에 빠질 위험이 있다.)
• 가까운 정점을 모두 저장 후 순서대로 방문해야 하므로 큐 자료구조를 사용한다.

너비 우선 탐색의 구현

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)

# 결과 : 1 2 3 8 7 4 5 6