너비 우선 탐색 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)를 모두 방문합니다.
다음은 DFS에 대해 설명한 글입니다.
[알고리즘] 깊이 우선 탐색(DFS) - Python
깊이 우선 탐색 Depth-First Search 깊이 우선 탐색(DFS)이란 그래프를 탐색하는 방법의 일종으로, root node에서 시작해서 깊이 방향(Depth)으로 확장하는 방식의 탐색을 말합니다. 깊이 방향이란, 한 노드
stevenkim1217.tistory.com
참고자료
https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
Introduction to Algorithms | Electrical Engineering and Computer Science | MIT OpenCourseWare
This course is an introduction to mathematical modeling of computational problems, as well as common algorithms, algorithmic paradigms, and data structures used to solve these problems. It emphasizes the relationship between algorithms and programming and
ocw.mit.edu
'컴퓨터 과학(Computer Science) > 알고리즘(Algorithm)' 카테고리의 다른 글
| [알고리즘] DAG 최단 경로 문제(DAG Shortest Path Problem) (0) | 2023.12.01 |
|---|---|
| [알고리즘] 깊이 우선 탐색(DFS) - Python (0) | 2023.11.10 |
| [알고리즘] 퀵 정렬 (Quick Sort) - Python (0) | 2023.10.28 |
| [알고리즘] 병합 정렬 (Merge Sort) - Python (0) | 2023.10.28 |
| [알고리즘] 삽입정렬(Insertion Sort) - Python (0) | 2023.10.28 |
