너비 우선 탐색(BFS)
An algorithm that explores a graph or tree level by level, visiting all neighbors of a node before moving to the next level.
◼︎ 너비 우선 탐색 BFS(Breadth First Search)
- 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘
- 시작 정점(Vertex)를 방문한 이후, 인접한 정점들을 모두 우선적으로 방문하는 탐색 알고리즘
- 즉, 깊게(Deep) 탐색하기 전에, 넓게(Wide) 탐색하는 알고리즘이다.
사용 상황
BFS(너비 우선 탐색)는 가장 가까운 노드부터 탐색하므로, 최단 경로를 찾는 문제에 적합하다.
두 노드 사이의 최단 경로를 찾을 때, 그래프에서 가장 가까운 아이템을 찾을 때 사용한다.
반면, DFS(깊이 우선 탐색)
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이므로, 모든 노드를 방문해야 하는 문제나, 경로의 깊이가 중요한 문제 등에 적합하다. 예를 들어, 미로 찾기 문제나 퍼즐을 해결하는 데 사용된다.
DFS와의 가장 큰 차이
DFS는 깊이 우선 탐색으로, 시작 노드에서 가장 멀리 떨어진 노드를 우선적으로 탐색한다. 반면에, BFS는 너비 우선 탐색으로, 시작 노드에서 가장 가까운 노드부터 탐색한다.
BFS의 특징
- 재귀적으로 동작하지 않는다.
- 이는 BFS가 모든 인접 노드를 먼저 방문하고, 그 인접 노드들의 인접 노드를 방문하는 방식으로 동작하기 때문이다. 이를 위해 BFS는 보통 큐를 사용하여 방문할 노드를 관리한다.
BFS는 왜 큐 자료 구조를 활용하는가?
알고리즘의 핵심 원칙, 즉 ‘가장 가까운 노드부터 탐색해 나가는 것’을 수행하기 위함이다.
큐는 ‘First In First Out’(FIFO)라는 원칙을 가진 자료구조로, 먼저 들어온 데이터가 먼저 나가는 구조를 가지고 있다. BFS에서는 시작 노드부터 시작하여 각 노드의 인접 노드들을 순서대로 방문하게 되는데, 이 때 방문할 노드들을 큐에 저장하게 된다.
예를 들어
시작 노드 A와 인접한 노드들 B, C, D가 있다고 가정해보자.
BFS를 수행하면, 먼저 A를 방문하고 그 다음으로 인접한 노드들 B, C, D를 큐에 넣는다.
이후 큐에서 노드를 하나씩 꺼내면서 그 노드의 인접 노드들을 다시 큐에 넣는다. 이 과정을 큐가 빌 때까지 반복하게 되면, 너비를 우선으로 모든 노드를 방문하게 된다.
큐가 빌 때까지
큐가 비어있다는 것은 더 이상 방문할 노드가 없다는 뜻이다.
방문한 각 노드의 인접 노드들을 큐에 추가한다. 따라서, 큐가 비어있다는 것 → 더 이상 방문할 인접 노드가 없다는 것
아래 표는 BFS 알고리즘의 동작 과정을 단계별로 표로 나타낸다면
| 단계 | 방문 노드 | 큐의 상태 |
|---|---|---|
| 1 | A | B, C, D |
| 2 | B | C, D, B의 인접 노드들 |
| 3 | C | D, B의 인접 노드들, C의 인접 노드들 |
| … | … | … |
BFS Java Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
private static void bfs(int N) {
//bfs는 큐로 구현
Queue<Integer> que = new LinkedList<>();
//큐에 현재 노드 삽입
que.add(N);
//방문 체크
visited[N] = true;
// 큐 빌 때까지
while (!que.isEmpty()) {
/**
* @Point 현재 노드 큐에서 poll 해야 함
*/
int nowNode = que.poll();
System.out.print(nowNode + " ");
for (int ele : list[N]) {
if (!visited[ele]) {
visited[ele] = true;
que.add(ele);
}
}
}
}
큐에서 현재 노드를 poll하는 과정
- BFS 알고리즘을 시작할 때, 큐에는 시작 노드만 들어있다. 그리고 이 노드는 큐에서 가장 먼저 나가게 될 노드이다.
- 알고리즘의 각 단계에서, 큐의 앞쪽에 있는 현재 노드를 poll(제거)하고 방문한다. 그리고 방문한 노드의 모든 인접 노드들을 찾아 큐에 추가하는데, 이때, 아직 방문하지 않은 노드만 큐에 추가한다.
- 이런 식으로 큐가 비어있을 때까지 계속하여 현재 노드를 poll하고 방문하며, 그 인접 노드들을 큐에 추가한다.
BFS 시간 복잡도
BFS의 시간 복잡도는 노드의 수와 간선의 수에 의해 결정된다.
1
2
O(V+E)
//여기서 V는 그래프의 노드 수를 나타내고, E는 그래프의 간선 수를 나타냄
이러한 시간 복잡도가 결정되는 이유는?
BFS가 그래프의 모든 노드와 간선을 정확히 한 번씩 검사하기 때문에 노드 수(V)와 간선 수(E)의 합에 비례한다.
인접행렬과 인접리스트를 사용한 BFS의 시간복잡도
인접행렬과 인접리스트는 그래프를 표현하는 방식에 따라 BFS의 시간복잡도가 달라진다.
인접행렬을 사용한 BFS
1
2
O(V^2)
// V는 노드의 수
인접행렬은 2차원 배열을 사용하여 그래프를 표현한다. BFS를 수행할 때, 각 노드를 방문하고 해당 노드와 연결된 모든 노드를 확인하기 위해, 행렬의 모든 요소를 확인해야 한다.
인접리스트를 사용한 BFS
1
O(V+E)
인접리스트는 각 노드를 헤드로 하는 연결 리스트로 그래프를 표현한다. BFS를 수행할 때, 각 노드를 방문하고 해당 노드와 연결된 노드만 확인하면 된다.
따라서, 인접리스트는 인접행렬에 비해 공간 효율성이 높으며, BFS를 수행하는 데 필요한 시간 복잡도도 낮다는 장점이 있다.
그래서 그래프 내에 적은 숫자의 간선을 갖는 희소 그래프의 경우, 인접 행렬보다 인접 리스트를 사용하는 것이 시간 복잡도를 줄일 수 있다.