BFS - 너비 우선 탐색

BFS는 너비 우선 탐색으로 Start Node와 가까운 노드 부터 탐색하는 알고리즘입니다. DFS와 반대인 탐색알고리즘이다. 아래 Graph를 통해 BFS에 대해 알아보자.

Graph

Graph 예시

Code로 보는 Graph

graph = [
    [],  # root_node
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

BFS 탐색하기

BFS 탐색 순서

간단한 BFS 알고리즘

from collections import deque

def bfs(graph, start, visited):
  queue = deque([start])
  visited[start] = True

  while queue:
    
    v = queue.pop()
    print(v, end=' ')

    for node in graph[v]:
      if not visited[node]:
        queue.appendleft(node)
        visited[node] = True


graph = [
    [],  # root_node
    [2, 3, 8], # 1의 Links
    [1, 7],    # 2의 Links
    [1, 4, 5], # 3의 Links
    [3, 5],    # 4의 Links
    [3, 4],    # 5의 Links
    [7],       # 6의 Links
    [2, 6, 8], # 7의 Links
    [1, 7]     # 8의 Links
]

visited = [False] * len(graph)

bfs(graph, 1, visited)

탐색 과정

1.  Start node는 1 -  1을 queue에 집어 넣고 방문함으로 표시한다. visited[1] = True

    queue => [1]
    visited => [False, True, False, False, False, False, False, False, False]

 

2.  queue에서 1을 빼고 1의 링크 노드들을 queue에 집어넣고 방문하지않은 노드를 방문한 노드로 표시한다. 

    visited[2] = True, visited[3] = True, visited[8] = True

    queue => [8, 3, 2] -> 1
    visited => [False, True, True, True, False, False, False, False, True]

 

3.  queue에서 2를 빼고 2의 링크 노드들을 queue에 집어넣고 방문하지않은 노드를 방문한 노드로 표시한다.

    visited[7] = True 

    queue => [7, 8, 3] -> 2
    visited => [False, True, True, True, False, False, False, True, True]

 

4.  queue에서 3를 빼고 3의 링크 노드들을 queue에 집어넣고 방문하지않은 노드를 방문한 노드로 표시한다.

    visited[4] = True,  visited[5] = True  

    queue => [5, 4, 7, 8] -> 3
    visited => [False, True, True, True, True, True, False, True, True]

 

5.  queue에서 8를 빼고 8의 링크 노드들을 queue에 집어넣고 방문하지않은 노드를 방문한 노드로 표시한다.  

    queue => [5, 4, 7] -> 8
    visited => [False, True, True, True, True, True, False, True, True]

 

6.  queue에서 7를 빼고 7의 링크 노드들을 queue에 집어넣고 방문하지않은 노드를 방문한 노드로 표시한다.

    visited[6] = True

    queue => [6, 5, 4] -> 7
    visited => [False, True, True, True, True, True, True, True, True]

 

7.  모든 노드를 방문했고 더이상 링크 노드들이 없으므로 queue에서 모든 노드가 제거되고 종료된다.

    queue => [] -> 6, 5, 4
    visited => [False, True, True, True, True, True, True, True, True]