Graph Traversal

그래프 탐색은 하나의 정점에서 시작하여 모든 정점들을 한 번씩 방문하는 작업이다. 대표적인 방법으로 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)가 있다. 두 알고리즘은 방문하는 순서가 완전히 다르며, 문제의 성격에 따라 적절한 방법을 선택해야 한다.

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

DFS는 갈 수 있는 데까지 깊게 가본 뒤, 더 이상 갈 곳이 없으면 뒤로 돌아와 다른 경로를 찾는 방식이다.

• 동작 원리: 현재 정점에서 연결된 미방문 정점 중 하나를 골라 즉시 이동한다. 더 이상 방문할 인접 정점이 없다면 마지막으로 방문했던 정점으로 되돌아가서(Backtracking) 탐색을 재개한다.
• 구현 방법: 주로 재귀 함수를 이용하거나 스택을 사용하여 구현한다.
• 특징: 모든 경로를 탐색해야 할 때 유리하며, 백트래킹과 결합하여 유망하지 않은 경로를 일찍 차단하는 용도로 자주 쓰인다. 위상 정렬이나 이분 매칭 등의 알고리즘에서도 핵심적으로 사용된다.

구현 코드

void DFS(int x) {
    visit[x] = true;
    printf("%d ", x); // 방문한 노드 출력

    for (int i = 1; i <= n; ++i) {
        // 연결되어 있고 아직 방문하지 않은 정점 탐색
        if (matrix[x][i] == true && visit[i] == false) {
            DFS(i);
        }
    }
    return;
}

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

BFS는 시작 정점에서 가까운 정점들을 먼저 모두 방문한 뒤, 멀리 있는 정점들을 차례로 탐색하는 방식이다.

• 동작 원리: 시작 정점으로부터 인접한 모든 정점을 먼저 방문한다. 그다음 방문했던 정점들에 인접한 정점들을 순차적으로 방문하며 탐색 범위를 넓혀간다.
• 구현 방법: 선입선출(FIFO) 구조인 큐를 사용하여 구현한다.
• 특징: 가중치가 없는 그래프에서 최단 경로를 찾는 데 최적이다. 위상 정렬 구현 시 진입 차수(in_degree)가 0인 노드부터 탐색하는 방식으로도 활용된다.

구현 코드

void BFS(int start) {
    int queue[MAX_IDX];
    int front = 0, rear = 0;

    // 시작 지점 설정
    visit[start] = true;
    queue[rear++] = start;

    while (front < rear) {
        int a = queue[front++]; // 큐에서 정점 하나를 꺼냄
        printf("%d ", a);

        for (int i = 1; i <= n; ++i) {
            // 인접한 정점 중 방문하지 않은 곳을 모두 큐에 삽입
            if (matrix[a][i] == true && visit[i] == false) {
                visit[i] = true;
                queue[rear++] = i;
            }
        }
    }
    return;
}

탐색 예시

아래와 같은 트리 형태의 그래프가 있다고 가정하자.

      1
    /   \
   2     3
  / \     \
 4   5     6

DFS 탐색 순서 (재귀 기준)

1. 1번에서 시작하여 왼쪽 자식인 2번으로 내려간다.
2. 2번에서 다시 깊게 들어가 4번을 방문한다.
3. 4번에서 더 갈 곳이 없으므로 2번으로 돌아와 5번을 방문한다.
4. 2번 근처 탐색이 끝났으므로 1번으로 돌아와 오른쪽 3번으로 간다.
5. 3번에서 6번을 방문한다.

• 결과: 1 -> 2 -> 4 -> 5 -> 3 -> 6

BFS 탐색 순서 (큐 기준)

1. 1번을 방문하고 큐에 넣는다.
2. 큐에서 1번을 꺼내며 인접한 2번, 3번을 순서대로 방문한다.
3. 큐에서 2번을 꺼내며 인접한 4번, 5번을 방문한다.
4. 큐에서 3번을 꺼내며 인접한 6번을 방문한다.

• 결과: 1 -> 2 -> 3 -> 4 -> 5 -> 6 (같은 깊이/레벨끼리 먼저 방문)

요약

구분	DFS (깊이 우선 탐색)	BFS (너비 우선 탐색)
자료구조	스택, 재귀 호출	큐 (Queue)
탐색 방향	수직적으로 깊게 탐색	수평적으로 넓게 탐색
주요 용도	경로의 특징 저장, 백트래킹	최단 거리 찾기, 레벨 탐색
장점	메모리 사용이 상대적으로 적음	최단 경로 보장 (가중치 없을 시)

• DFS: 스택(혹은 재귀 호출)을 활용하며, 한 경로를 끝까지 파고들 때 유리하다. $O(V^2)$ (인접 행렬 기준)의 시간 복잡도를 가진다.
• BFS: 큐를 활용하며, 시작점에서 가까운 노드부터 탐색하므로 가중치가 없는 그래프에서 최단 거리를 찾는 데 적합하다. 시간 복잡도는 동일하게 $O(V^2)$이다.