[알고리즘]그래프 탐색하기: BFS & DFS
그래프의 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제를 그래프 순회 문제(graph traversal problem)이라고 합니다.
그래프 순회 문제는 그래프에서 특정 정점을 찾기 위한 용도로 사용될 수 있기 때문에 그래프 탐색 문제(graph search problem)이라고도 합니다.
그래프 탐색에서 아직 방문하지 않은 노드들 중 다음으로 살펴볼 노드들의 리스트를 open list, 방문한 노드들의 리스트를 closed list라고 말합니다.
그래프 탐색 알고리즘으로 너비 우선 탐색(BFS, Breadth-First Search)와 깊이 우선 탐색(DFS, Depth-First Search)가 있습니다.
- 너비 우선 탐색(BFS, Breadth-First Search)
BFS는 탐색 과정에서 방문할 노드의 순서를 기억할 자료구조로 Queue를 사용합니다. 즉 open list로 queue를 사용합니다.
closed list는 visit을 저장하는 배열을 사용하여 방문한 노드는 방문 표시를 해야합니다. 방문한 노드를 또 방문하는 것을 막기 위해서입니다.
시작 노드와 같은 거리, 즉 인접한 노드들의 방문 순서는 임의로 정해도 되지만, 반드시 시작 노드에서 가까운 노드부터 방문해야 합니다.
즉, 현재 노드에서 모든 자식 노드를 먼저 방문한 뒤, 손자 노드를 방문합니다.
[탐색 과정]
(1) 시작 노드를 Queue에 push
(2) Queue에서 다음 살펴볼 노드 v를 pop
(3) 노드 v를 이전에 방문했는지 확인(방문했다면 (2)번으로)
(4) 노드 v 방문 표시
(5) 노드 v에 인접한 노드들 중 아직 방문하지 않은 노드 w를 Queue에 push
(6) Queue가 empty일 때까지 (2)~(5) 과정 반복
- 장단점
| 장점 | 단점 |
| 1. 최단 경로 존재 시, 항상 최단 경로를 찾아줌 2. 검색 속도는 DFS보다 빠름 3. 그래프의 깊이가 얕고 노드의 수가 적을 때 적합 |
1. 그래프의 깊어질수록 상당한 메모리가 필요함 2. 유한 그래프에서 해가 없을 때, 그래프를 모두 탐색한 후에도 해를 찾을 수 없음 3. 무한 그래프에선 해를 찾을 수도 없고 탐색이 끝나지 않음 |
- 깊이 우선 탐색(DFS, Depth-First Search)
DFS는 탐색 과정에서 방문할 노드의 순서를 기억할 자료구조로 Stack을 사용합니다. 즉 open list로 stack을 사용합니다. 또는 재귀함수를 사용합니다.
역시 closed list는 visit을 저장하는 배열을 사용하여 방문한 노드는 방문 표시를 합니다. 방문한 노드를 또 방문하는 것을 막기 위해서입니다.
BFS가 시작 노드에서 점차 탐색 범위를 넓혀 나가는 방식이라면, DFS는 시작 노드에서 시작하여 특정 경로를 따라 가능한 깊이 있는 노드을 재귀적으로 먼저 방문하는 방식입니다.
[탐색 과정]
(1) 시작 노드를 Stack에 push
(2) Stack에서 다음 살펴볼 노드 v를 pop
(3) 노드 v를 이전에 방문했는지 확인(방문했다면 (2)번으로)
(4) 노드 v 방문 표시
(5) 노드 v에 인접한 노드들 중 아직 방문하지 않은 노드 w를 Stack에 push
(6) Stack이 empty일 때까지 (2)~(5) 과정 반복
- 장단점
| 장점 | 단점 |
| 1. BFS보다 간단 2. 저장 공간이 많이 요구되지 않음 3. 목표 노드가 깊이 있을 때 빠르게 찾을 수 있음 |
1. 검색 속도 자체는 BFS보다 느림 2. 찾은 해가 최적의 해라는 보장이 없음 |
- BFS vs DFS 비교
| BFS | DFS |
| Queue로 구현 | Stack 또는 재귀함수로 구현 |
| 항상 최적 해 | 최적의 해라는 보장은 없음 |
| 그래프 규모가 작을 때 | 그래프 규모가 클 때 |
| 최단 경로를 찾을 때 사용 | 특정 목표 노드를 찾을 때 사용 |