[Algorithm] 너비 우선 탐색(BFS)은 뭐야?

너비 우선 탐색 BFS는 Breadth First Search의 약자이고, 너비를 우선으로 탐색하는 알고리즘이다.  DFS는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식이었다면 BFS는 가까운 노드를 우선으로 탐색한다. 블루투스나 와이파이 같은 원리랑 비슷하다.

 

다음은 너비 우선 탐색의 과정을 그림으로 나타낸 것이다.

너비 우선 탐색 1번째

 

시작 노드인 '1'을 큐에 넣어주고, 방문 처리를 한다. 초록색은 처리 중인 노드, 파란색은 방문 처리된 노드를 표현한다.

 

너비 우선 탐색 2번째

큐에서 '1'을 꺼내 주고 방문하지 않은 인접 노드 '3'을 큐에 넣어주고 방문 처리를 한다.

 

너비 우선 탐색 3번째

큐에서 '3'을 꺼내주고 방문하지 않은 인접 노드 '4', '5'를 큐에 넣어주고 방문 처리를 한다.

 

너비 우선 탐색 4번째

큐에서 '4'를 꺼내준다. 이때 방문하지 않은 인접 노드가 존재하지 않으므로 무시한다.

 

너비 우선 탐색 5번째

큐에서 '5'를 꺼낸다. 방문하지 않은 인접 노드 '2'를 큐에 넣어주고 방문 처리한다.

 

너비 우선 탐색 6번째

큐에서 '2'를 꺼낸다. 이때 방문하지 않은 인접 노드가 존재하지 않고 큐에 더 이상 꺼내 줄 노드가 존재하지 않으므로 종료된다.

 

너비 우선 탐색 7번째

최종적으로 너비 우선 탐색이 진행한 모습이다. 결과적으로 노드의 방문 순서는 1 - 3  - 4 - 5 - 2가 된다.

 

다음은 너비 우선 탐색을 코드로 표현한 것이다.

 

from collections import deque
 
def bfs(graph, start, visited):
  queue = deque([start])
  visited[start] = True
 
  while queue:
    v = queue.popleft()
    print(v)
 
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True
 
graph = [
  [],
  [3],
  [5],
  [4,5],
  [3],
  [2,3]
]
 
visited = [False] * 6
bfs(graph, 1, visited)

 

참고자료

이것이 취업을 위한 코딩 테스트다 with 파이썬