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

그래프 탐색 알고리즘 중 DFS에 이어 BFS에 대해 포스팅한다.

DFS(깊이 우선 탐색) 알고리즘

 

1. BFS(너비 우선 탐색) 알고리즘이란?

• 그래프 탐색 알고리즘의 한 종류
• 그래프 탐색이란 한 정점으로부터 시작하여 다른 정점을 차례대로 모두 한번씩 방문하는 것
• DFS가 임의의 정점에서 시작하여 다른 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법이라면
• BFS는 임의의 정점에서 시작하여 다음 레벨로 진입하기 전 인접한 분기를 모두 탐색하는 방법

---

2. BFS의 특징

• 깊게 탐색하기 전에 넓게 탐색
• BFS는 재귀로 구현할 수 없음
• 방문한 노드를 저장하고 차례대로 꺼내면서 탐색하므로 큐(선입선출)를 사용하여 구현함

---

3. BFS의 장점

• 가장 먼저 구한 해가 최단 경로임을 보장
• 최단 경로가 존재한다면 특정 경로의 길이가 무한이라도 최단 경로를 찾을 수 있음

4. BFS의 단점

• 큐에 탐색할 노드를 저장하므로 저장공간이 많이 소요
• 노드가 많을수록 효율이 떨어짐 

---

5. BFS를 써야 하는 문제

 1) 두 노드 사이의 최단 경로 구하기 또는 임의의 경로 구하기

 2) 검색 대상의 규모가 크지 않은 경우, 검색 대상이 시작 지점으로부터 멀지 않은 경우

 3) 대상을 검색해야 하는 경우(조건을 만족하는 순회에 초점을 둔 DFS보다 유리)

 

6. 구현

스택과 재귀 두가지 방법으로 구현할 수 있었던 DFS와 달리 BFS는 큐를 사용한 반복구조로 구현하여야만 한다.

import collections
queue = collections.deque()
def bfs(start_node):
    visited = [start_node]
    queue.append(start_node)
    while queue:
        parent = queue.popleft()
        for child in graph[parent]:
            if child not in visited:
                queue.append(child)
                visited.append(child)
	return visited

참고)

collections 모듈에 구현된 deque자료형을 사용하였다.

리스트로도 구현할 수 있으나 큐의 연산을 구현하기 위해서는 pop(0)를 사용하여야 한다.

리스트의 pop연산은 리스트의 요소를 전부 복사하여야 하므로 시간 복잡도가 O(n)이다.

따라서 파이썬에서 queue를 성능저하 없이 사용하기 위해서는 deque자료형을 사용하고, 이 경우 O(1)에 연산이 가능하다.