BFS (너비 우선 탐색)

BFS는 Breadth-First Search의 약자이며 너비 우선으로 탐색하는 알고리즘이다. BFS는 Queue 자료구조를 이용한다. BFS는 첫번째 값과 인접한 노드의 값들을 먼저 queue에 넣어 처리후 그 다음 노드들을 똑 같이 탐색해 나간다.

Python 예제:

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)

# ANSWER = 1 2 3 8 7 4 5 6

위의 예제같이 BFS는 Collections의 deque를 이용한다. 이는 시간 복잡도의 효율성을 높이기 위함이다.