그래프(Graph)는 대표적인 비선형 데이터 구조입니다. 이 자료구조에서는 값들을 노드(Node)에 저장하고, 노드들은 서로 다른 간선(Edge)으로 연결됩니다. 그래프 구조에 데이터를 저장할 수 있는 것처럼, 저장된 데이터를 실제로 활용하려면 그래프 내부에서 원하는 요소를 검색(탐색)하는 방법도 필요합니다.
그래프에서 탐색을 수행하는 방법은 크게 두 가지가 있습니다. 바로 너비 우선 탐색(Breadth First Search, BFS)과 깊이 우선 탐색(Depth First Search, DFS)입니다.
너비 우선 탐색(BFS, Breadth First Search)
너비 우선 탐색(BFS)은 주어진 그래프의 모든 노드를 방문하기 위해 사용되는 순회(traversal) 알고리즘입니다. 이 알고리즘에서는 먼저 하나의 노드를 선택한 뒤, 해당 노드에 인접한 모든 노드들을 하나씩 차례로 방문합니다.
인접한 정점들을 모두 처리하고 나면, 다음 정점으로 이동하여 같은 방식으로 그 정점의 인접 정점들을 다시 확인합니다.
BFS를 구현하려면 큐(Queue) 자료구조가 반드시 필요합니다. 동작 과정은 다음과 같습니다.
- 탐색을 시작하는 정점의 인접 정점들을 모두 큐에 추가합니다.
- 인접 정점 방문이 끝나면 큐에서 하나의 항목을 꺼냅니다(dequeue).
- 꺼낸 정점을 기준으로 다시 인접 정점들을 탐색하며, 이 과정을 큐가 빌 때까지 반복합니다.
이러한 특성 덕분에 BFS는 시작 정점에서 가까운 노드부터 순서대로 방문하게 되며, 최단 경로 탐색 등에 널리 활용됩니다.
깊이 우선 탐색(DFS, Depth First Search)
깊이 우선 탐색(DFS) 역시 그래프 순회 알고리즘의 하나입니다. 시작 정점이 주어지면, 인접한 정점을 발견하는 즉시 그 정점으로 먼저 이동하여 같은 방식으로 계속 탐색을 진행합니다.
즉, 갈 수 있는 만큼 한 방향으로 깊숙이 들어간 후, 더 이상 진행할 곳이 없으면 백트래킹(backtracking)을 통해 이전 정점들로 되돌아가 아직 탐색하지 않은 새로운 경로를 찾습니다.
DFS를 구현하는 방법은 두 가지입니다.
- 반복문(iterative) 방식: 명시적으로 스택(Stack) 자료구조를 사용해야 합니다.
- 재귀(recursive) 방식: 별도의 외부 스택이 필요하지 않으며, 함수 호출 시 시스템이 관리하는 내부 스택(콜 스택)을 활용해 구현할 수 있습니다.
BFS와 DFS 비교 요약
| 구분 | BFS | DFS |
|---|---|---|
| 핵심 자료구조 | 큐(Queue) | 스택(Stack) 또는 재귀 호출 |
| 탐색 방향 | 가까운 노드부터 넓게 확장 | 한 경로를 끝까지 깊이 진입 |
| 주요 활용 | 최단 경로 탐색, 레벨 순회 | 경로 존재 여부 확인, 위상 정렬, 사이클 검출 |
두 알고리즘 모두 그래프 이론의 기초이자 가장 중요한 탐색 기법입니다. 문제의 성격에 따라 적절한 방식을 선택하는 것이 효율적인 알고리즘 설계의 핵심입니다.