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

너비 우선 탐색 Breadth-First Search

너비 우선 탐색(BFS)이란 그래프를 탐색하는 방법의 일종으로, root node에서 시작해서 너비 방향(Breadth)으로 확장하는 방식의 탐색을 말합니다.

넓게 확장하는 것이란, 한 노드에서 인접한 모든 노드를 우선 탐색하는 것을 말합니다. 인접해있는 모든 노드의 탐색을 마친 후, 다음 노드에서의 너비 탐색을 시작합니다.

Level

탐색을 진행할 때 인접한 노드를 차례대로 모두 탐색하고 다음 인접 노드로 넘어간다고 했는데, 이때 같은 층위에 있는 인접 노드들을 level로 묶습니다. 그림을 보시면, root에서 시작해 root에 바로 인접해 있는 노드들을 level 1이라고 부르고, 이 level 1에 속해있는 노드들의 parent는 당연히 root node인 s가 됩니다. level 1과 바로 인접한 노드들의 집합을 level 2라고 부릅니다.

이전 level에서 방문했으면 다시 돌아가지 않습니다. level이 커지는 쪽으로 단방향 증가 탐색합니다.

Frontier

BFS에서 탐색을 펼쳐 나가기 위해 Frontier라는 용어를 사용합니다. 말 그대로 개척자의 역할을 하는데요. 탐색을 현재 이어나가고 있는 level의 노드를 Frontier list에 담아둡니다. Frontier List를 선언한 뒤, 이 Frontier을 계속해서 업데이트 해 나가며 탐색을 진행합니다.

Pseudo Code

BFS의 Pseudo Code는 다음과 같습니다.

• 우선, 탐색에 쓰이는 각 list나 index를 초기화합니다. 이때 level과 parent는 dictionary를, frontier은 list를 사용합니다.

• 현재 frontier에 들어있는 node에 대해서, 만약 현재 탐색하고 있는 node가 방문하지 않은 노드라면 (not in level), level과 parent를 업데이트 해주어 방문 처리를 해줍니다. 그 다음 방문 처리된 node를 next 리스트에 담고,

• 이 next 리스트가 다음 번의 frontier가 됩니다.

Visualization

BFS를 시각화 하기 위해 코드를 추가해보겠습니다.

• “.color”을 통해 node의 색을 업데이트 해줍니다.
  • WHITE: 방문하지 않은 노드
  • GRAY: 방문 중인 노드
  • BLACK: 방문을 완전히 마친 노드
• “.d”는 시작 노드인 s에서부터의 distance를 의미합니다. (미방문 노드는 처음에 ∞로 초기화합니다.)
• “.파이”는 predecessor, 즉 parent을 의미합니다.
• 현재 방문 중인 노드(회색 노드)를 Q에 enqueue합니다. 방문을 마칠 시(검정색으로 칠할 시) dequeue합니다.

위 코드를 통해 BFS를 시각화해보면 다음과 같습니다.

(a) root 노드인 s만 0으로 초기화하고, 나머지 미방문 노드는 모두 ∞로 초기화합니다.

(b) s의 인접 노드인 r과 w를 방문합니다. s와의 거리가 한 칸이기 때문에 distance는 1로 업데이트합니다. s는 방문을 마쳤기 때문에 검정색으로 칠하고, 현재 방문 중인 r과 w는 회색으로 칠합니다.

(c) Q에서 w를 먼저 dequeue하여 탐색합니다. w에 연결되어 있는 노드를 업데이트합니다.

(d) 그 다음으로 r을 dequeue하여 탐색합니다. r에 연결되어 있는 노드를 업데이트합니다.

• 위와 같은 방식으로 Q안에 있는 노드에 대해서 탐색합니다.
• Q에 노드가 더 이상 없어질 때까지 반복합니다.

Time Complexity

대부분의 그래프 알고리즘이 그러하듯 O(V+E) 의 시간복잡도를 가집니다. 모든 edge(E)를 한 번씩 검사하고, 각 vertex(V)를 모두 방문합니다.

참고자료: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/