DFS와 BFS

DFS와 BFS는 그래프 탐색 알고리즘 중 하나입니다.

깊이 우선 탐색(DFS, Depth-First Search)

DFS는 Depth-First Search, 깊이 우선 탐색이라고도 불리며 그래프의 한 노드에서 시작하여 해당 분기의 노드를 완전히 탐색하고 다음 분기로 넘어가는 방식을 말합니다.

쉽게 말해 루트 노드에서 시작하여 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되었을 떄 가장 가까운 분기로 돌아와 다시 탐색하는 방법입니다. 보통 모든 노드를 방문하여야 하는 경우 사용하게 됩니다.

DFS의 시간복잡도는 V를 정점의 수, E를 간선의 수라 할 때 $O(|V| + |E|)$이다.

너비 우선 탐색(BFS, Breadth-First Search)

BFS는 Breadth-First Search, 너비 우선 탐색이라고도 불리며 그래프의 한 노드에서 시작하여 인접한 노드를 먼저 탐색하고 그 후에 멀리 떨어져 있는 노드를 탐색하는 방식을 말합니다.

루트 노드에서 시작하여 해당 노드의 이웃 노드를 모두 방문하고 그 후 다음 노드로 넘어가는 방법입니다. 보통 최단경로를 구하거나 임의의 경로를 구하는 상황에 사용하게 됩니다.

BFS의 시간복잡도는 $O(|V| + |E|)$로 DFS와 동일합니다.