콘텐츠로 이동

깊이 우선 탐색

깊이 우선 탐색은 주요 그래프 알고리즘 중 하나입니다.

깊이 우선 탐색은 그래프에서 시작 정점 $u$부터 각 정점까지의 사전순으로 가장 앞선 경로를 찾습니다. 깊이 우선 탐색은 트리에서는 최단 경로도 찾지만(단순 경로가 하나만 존재하기 때문입니다), 일반 그래프에서는 그렇지 않습니다.

이 알고리즘은 $O(m + n)$ 시간에 동작하며, 여기서 $n$은 정점의 개수이고 $m$은 간선의 개수입니다.

알고리즘 설명

DFS의 핵심 아이디어는 그래프에서 가능한 한 깊이 들어가다가, 방문하지 않은 인접 정점이 없는 정점에 도달하면 되돌아오는 것입니다.

이 알고리즘은 재귀적으로 설명하고 구현하기가 매우 쉽습니다. 먼저 한 정점에서 탐색을 시작합니다. 정점을 방문한 뒤에는, 아직 방문하지 않은 각 인접 정점에 대해 다시 DFS를 수행합니다. 이렇게 하면 시작 정점에서 도달할 수 있는 모든 정점을 방문하게 됩니다.

자세한 내용은 구현을 참고하십시오.

  • 그래프에서 시작 정점 $u$부터 모든 정점까지의 임의의 경로를 찾습니다.

  • 그래프에서 시작 정점 $u$부터 모든 정점까지의 사전순으로 가장 앞선 경로를 찾습니다.

  • 트리에서 한 정점이 다른 정점의 조상인지 확인합니다:

    각 탐색 호출의 시작과 끝에서 각 정점의 진입 "시각"과 탈출 "시각"을 기록합니다. 이제 임의의 정점 쌍 $(i, j)$에 대한 답을 $O(1)$에 구할 수 있습니다. 정점 $i$가 정점 $j$의 조상일 필요충분조건은 $\text{entry}[i] < \text{entry}[j]$이고 $\text{exit}[i] > \text{exit}[j]$인 것입니다.

  • 두 정점의 최소 공통 조상(LCA)을 찾습니다.

  • 위상 정렬:

    일련의 깊이 우선 탐색을 수행하여 $O(n + m)$ 시간에 각 정점을 정확히 한 번씩 방문합니다. 원하는 위상 순서는 정점들을 탈출 시각의 내림차순으로 정렬한 것입니다.

  • 주어진 그래프에 사이클이 없는지 확인하고, 그래프에서 사이클을 찾습니다. (아래에서 설명하듯이 각 연결 요소에서 역방향 간선을 세어 확인합니다.)

  • 방향 그래프에서 강한 연결 요소를 찾습니다:

    먼저 그래프를 위상 정렬합니다. 그런 다음 그래프를 전치하고, 위상 정렬로 정해진 순서대로 다시 일련의 깊이 우선 탐색을 수행합니다. 각 DFS 호출마다 그 호출로 만들어진 요소가 하나의 강한 연결 요소입니다.

  • 무방향 그래프에서 브리지 찾기:

    먼저 일련의 깊이 우선 탐색을 수행하면서 각 간선을 지나갈 때 지나간 방향으로 방향을 부여하여, 주어진 그래프를 방향 그래프로 변환합니다. 둘째로, 이 방향 그래프에서 강한 연결 요소를 찾습니다. 브리지는 양 끝점이 서로 다른 강한 연결 요소에 속하는 간선입니다.

그래프 간선의 분류

그래프 $G$의 간선 $(u,v)$를 끝 노드 $u$와 $v$의 진입 시각과 탈출 시각을 이용해 분류할 수 있습니다. 이러한 분류는 브리지 찾기나 단절점 찾기와 같은 문제에 자주 사용됩니다.

DFS를 수행하면서 만나는 간선을 다음 규칙에 따라 분류합니다:

$v$를 아직 방문하지 않은 경우:

  • 트리 간선 - $v$를 $u$ 다음에 방문한다면 간선 $(u,v)$를 트리 간선이라고 합니다. 다시 말해, $v$를 처음 방문하고 있고 $u$를 현재 방문 중이라면 $(u,v)$를 트리 간선이라고 합니다. 이러한 간선들은 DFS 트리를 이루므로 트리 간선이라는 이름이 붙었습니다.

$v$를 $u$보다 먼저 방문한 경우:

  • 역방향 간선 - $v$가 $u$의 조상이라면 간선 $(u,v)$는 역방향 간선입니다. $v$에 이미 진입했지만 아직 탈출하지 않았다면, 그리고 그 경우에만 $v$는 조상입니다. (DFS의 재귀에서) 조상 $v$에서 자손 $u$로 가는 경로가 있고 자손 $u$에서 조상 $v$로 가는 간선(역방향 간선)이 있으므로, 역방향 간선은 사이클을 완성하며 이로써 사이클이 형성됩니다. 역방향 간선을 이용하여 사이클을 검출할 수 있습니다.

  • 순방향 간선 - $v$가 $u$의 자손이라면 간선 $(u, v)$는 순방향 간선입니다. 다시 말해, 이미 $v$를 방문하고 탈출했으며 $\text{entry}[u] < \text{entry}[v]$라면 간선 $(u,v)$는 순방향 간선이 됩니다.

  • 교차 간선: $v$가 $u$의 조상도 자손도 아니라면 간선 $(u, v)$는 교차 간선입니다. 다시 말해, 이미 $v$를 방문하고 탈출했으며 $\text{entry}[u] > \text{entry}[v]$라면 $(u,v)$는 교차 간선입니다.

정리. $G$를 무방향 그래프라고 합시다. 그러면 $G$에 대해 DFS를 수행할 때 만나는 모든 간선은 트리 간선 또는 역방향 간선으로 분류됩니다. 즉, 순방향 간선과 교차 간선은 방향 그래프에만 존재합니다.

$(u,v)$를 $G$의 임의의 간선이라 하고, 일반성을 잃지 않고 $u$를 $v$보다 먼저 방문한다고, 즉 $\text{entry}[u] < \text{entry}[v]$라고 가정합시다. DFS는 간선을 한 번만 처리하므로, 간선 $(u,v)$를 처리하여 분류하는 방법은 다음 두 가지뿐입니다:

  • 간선 $(u,v)$를 처음 탐색하는 방향이 $u$에서 $v$로 가는 방향인 경우입니다. $\text{entry}[u] < \text{entry}[v]$이므로, DFS의 재귀적 특성에 따라 노드 $u$를 탈출하기 위해 "호출 스택을 거슬러 올라가기" 전에 노드 $v$가 완전히 탐색되고 탈출됩니다. 따라서 DFS가 간선 $(u,v)$를 $u$에서 $v$ 방향으로 처음 탐색할 때 노드 $v$는 아직 방문되지 않은 상태여야 합니다. 그렇지 않다면 노드 $u$와 $v$가 이웃이므로, 탐색은 노드 $v$를 탈출하기 전에 $(u,v)$를 $v$에서 $u$ 방향으로 탐색했을 것이기 때문입니다. 그러므로 간선 $(u,v)$는 트리 간선입니다.

  • 간선 $(u,v)$를 처음 탐색하는 방향이 $v$에서 $u$로 가는 방향인 경우입니다. 노드 $u$를 노드 $v$보다 먼저 발견했고 간선은 한 번만 처리하므로, 간선 $(u,v)$를 $v$에서 $u$ 방향으로 탐색할 수 있는 유일한 경우는 간선 $(u,v)$를 거치지 않는 $u$에서 $v$로의 다른 경로가 존재하는 경우이며, 이때 $u$는 $v$의 조상이 됩니다. 따라서 간선 $(u,v)$는 자손 $v$에서 아직 탈출하지 않은 조상 $u$로 향하므로 사이클을 완성합니다. 그러므로 간선 $(u,v)$는 역방향 간선입니다.

간선 $(u,v)$를 처리하는 방법은 위에서 설명한 두 가지 경우와 그에 따른 분류뿐이므로, $G$에 대해 DFS를 수행할 때 만나는 모든 간선은 트리 간선 또는 역방향 간선으로 분류됩니다. 즉, 순방향 간선과 교차 간선은 방향 그래프에만 존재합니다. 이로써 증명이 완료됩니다.

구현

vector<vector<int>> adj; // graph represented as an adjacency list
int n; // number of vertices

vector<bool> visited;

void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u])
            dfs(u);
    }
}
다음은 깊이 우선 탐색의 가장 단순한 구현입니다. 응용 부분에서 설명한 것처럼 진입 시각과 탈출 시각, 그리고 정점의 색도 함께 계산하면 유용할 수 있습니다. 아직 방문하지 않은 정점은 모두 색 0으로, 방문한 정점은 색 1로, 이미 빠져나온 정점은 색 2로 칠합니다.

다음은 이러한 값들을 추가로 계산하는 일반적인 구현입니다:

vector<vector<int>> adj; // graph represented as an adjacency list
int n; // number of vertices

vector<int> color;

vector<int> time_in, time_out;
int dfs_timer = 0;

void dfs(int v) {
    time_in[v] = dfs_timer++;
    color[v] = 1;
    for (int u : adj[v])
        if (color[u] == 0)
            dfs(u);
    color[v] = 2;
    time_out[v] = dfs_timer++;
}

연습 문제