그래프에서 깊이 우선 탐색(Depth-First Search, DFS)는 그래프를 탐색하는 방법 중 하나다. 이름에서 알 수 있듯이 DFS는 최대한 깊게 들어갔다가 다시 나오는 탐색 방식이다. 정확한 동작 방식은 다음과 같다.
- 시작 정점을 방문하고 '방문함'으로 표시
- 시작 정점과 연결되어 있는 정점 중 아직 방문하지 않는 정점을 시작 정점으로 놓고 1을 반복
- 연결되어 있고 방문하지 않은 정점이 없다면 이전 정점으로 돌아가 다시 2를 반복
- 모든 정점을 방문했으면 탐색을 종료
이것을 시각화하면 다음과 같다. 1번 정점을 시작 정점이라고 할 때, 연결되어 있는 정점인 2를 방문하고, 2에서는 5를 방문하고, 다시 돌아와 6, 9... 이런 식으로 방문하기 때문에 총 탐색 순서는 1-2-5-6-9-7-10-3-4-11
이 된다.
DFS의 구현
그래프를 인접 행렬로 표현했을 때는 다음과 같이 구현할 수 있다.
bool adj[MAX][MAX]; // 인접 행렬
bool visited[MAX]; // 방문 기록 배열
int n; // 정점의 수
void dfs(int v) {
visited[v] = 1;
for (int i = 1; i <= n; i++) {
// 연결되어 있고 방문하지 않았다면 방문
if (adj[v][i] && !visited[i]) dfs(i);
}
}
최소한 모든 정점에 대해서 한번씩은 dfs(i)
를 호출해야 하고, 연결된 정점을 확인하기 위해서 모든 정점을 순회해야 하므로 시간 복잡도는 $O(V^2)$가 된다.
인접 리스트로 표현할 경우에는 다음처럼 구현할 수 있다.
vector<int> adj[MAX]; // 인접 리스트
bool visited[MAX];
void dfs(int v) {
visited[v] = 1;
for (int i = 0; i < adj[v].size(); i++) {
int nxt = adj[v][i];
if (!visited[nxt]) dfs(nxt);
}
}
모든 정점에 대해 한번씩은 dfs(i)
를 호출하고, 재귀로 호출하는 횟수는 간선의 개수와 같기 때문에 시간 복잡도는 $O(V+E)$이다.
컴포넌트의 개수 구하기
깊이 우선 탐색의 특성상, 한 정점에서 시작하면 같은 컴포넌트에 속하는 정점들만 방문할 수 있다. 그래프 하나가 여러 개의 컴포넌트로 이루어져 있을 때는 그 수를 어떻게 구할까?
모든 정점에 대해 DFS를 하면서 카운트를 해 주면 된다. 다만 이미 방문된 정점은 앞서 세어진 컴포넌트에 속하는 정점이므로 방문하지 않은 새로운 정점에 대해서만 DFS를 돌린다.
vector<int> adj[MAX];
bool visited[MAX];
int n; // 정점의 수
void dfs(int v) {
visited[v] = 1;
for (int i = 0; i < adj[v].size(); i++) {
int nxt = adj[v][i];
if (!visited[nxt]) dfs[nxt];
}
}
int countComponent() {
int ret = 0;
for (int i = 1; i <= n; i++) {
if (!visited[i]) dfs(i), cnt++;
}
return ret;
}