[Algorithm] 너비 우선 탐색 (Breadth First Search)

1. 개요

너비 우선 탐색 (Breadth-First Search) 은 비선형 자료를 특정 노드에서 시작하여 하위 노드보다 인접 노드를 먼저 방문하며 탐색하는 방식을 의미한다.

2. 의의

너비 우선 탐색 은 다음의 경우에 유용하게 사용될 수 있다.

너비 우선 탐색의 의의

1. 최단 경로 탐색
2. 층별 탐색
3. 최소 신장 트리 판단

3. 조건

너비 우선 탐색의 조건

1. 비선형 자료 (그래프, 트리) 의 탐색
2. 추가 메모리 공간 (자료 구조 Queue 사용)
3. 탐색 시작 지점 정의
4. 방문 여부 확인

4. 구현

너비 우선 탐색 은 반복문과 Queue 를 이용하여 구현할 수 있다.

1. 탐색 시작 노드를 설정하고 Queue 에 삽입한다.
2. Queue 를 dequeue 하여 얻은 노드를 탐색한다.
3. 탐색을 완료한 노드를 기록한다.
4. 현재 탐색 노드의 인접 노드들을 Queue 에 enqueue 한다.
   3.1. 이때 탐색 완료로 기록된 노드는 제외한다.
5. Queue 가 비었는지 확인한다.
   5.1. 비었을 경우, 탐색을 종료한다.
   5.2. 비어있지 않을 경우, [절차 2]로 이동한다.

5. 예시) 너비 우선 탐색 순서 출력

특정 그래프를 너비 우선으로 탐색할 때의 순서를 출력하는 코드를 작성해보자.

# 탐색할 그래프
graph = {
  0: [1, 2, 5],
  1: [0, 2, 4],
  2: [0, 1, 4, 5],
  3: [6],
  4: [1, 2, 5],
  5: [0, 2, 4, 6],
  6: [3, 5],
}

# 탐색할 값
s = int(input('s: '))

def breadth_first_search(graph, s):
  # queue 자료구조 사용
  queue = deque([s])

  # 탐색한 노드 저장
  visited = []

  # queue 가 빌 때까지 반복
  while queue:

    # dequeue 한 값을 탐색
    node = queue.popleft()

    # 탐색한 노드일 경우 이후 과정 생략
    if node in visited: continue

    # 탐색 기록 작성
    visited.append(node)

    # 탐색 노드의 인접 노드들을 큐에 enqueue
    for child in graph[node]:
      if child in visited + queue: continue
      queue.append(child)

  return visited

print(*breadth_first_search(graph, s))

5.1. 예시 입력1

• 입력

s: 1

• 출력

1 0 2 4 5 6 3

5.2. 예시 입력2

• 입력

s: 3

• 출력

3 6 5 0 2 4 1

6. 시간복잡도

이제 너비 우선 탐색 의 시간복잡도를 알아보자.

먼저 정점의 개수를 $V$ 간선의 개수를 $E$ 라고 할 때, 세부 연산들에 대하여 각각 다음의 시간복잡도를 가진다.

• 정점 방문: $O(V)$
• 간선 처리: $O(E)$
• Queue 연산: $O(V)$

따라서 위 시간복잡도의 총합이 최종 시간복잡도로 다음과 같다.

$$
O(V + E)
$$

6.1. 최악, 최선, 평균 시간복잡도

위 알고리즘은 최악, 최선, 평균 시간복잡도가 모두 같다. 각각의 경우 모두 모든 정점과 모든 간선을 탐색해야 함은 동일하기 때문이다.

최악	평균	최선
$O(V + E)$	$\Theta(V + E)$	$\Omega(V + E)$

---

관련 포스팅

• [Algorithm] 탐색 (Search)
• [Algorithm] 완전 탐색, 브루트 포스 (Brute Force)
• [Algorithm] 깊이 우선 탐색 (Depth First Search)