[알고리즘] 깊이 우선 탐색 (Depth-First Search, DFS)

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

그래프 순회 방식 중 하나.

시작 노드에서부터 출발하여 출발한 그래프의 간선을 따라 이동해가며 도달 가능한 모든 노드를 처리.

단일한 경로를 따라 순회. 그 후 이전 노드로 돌아가 그래프의 다른 부분을 탐색.

해를 구할 수 있지만, 그렇게 구해진 해가 최적해라는 보장은 없음.

 

시간복잡도의 경우 O(n+m)

여기서 n은 노드의 개수, m은 간선의 개수.

 

---

과정

시작 노드에서부터 출발하여 출발한 그래프의 간선을 따라 이동해가며 도달 가능한 모든 노드를 처리.

단일한 경로를 따라 순회. 그 후 이전 노드로 돌아가 그래프의 다른 부분을 탐색.

 

1번 노드에서 시작한다고 해보자.

 

1번 노드에서 2번 노드로 이동한다.

 

2번 노드에서 3번 노드로 이동한다.

 

3번 노드에서 5번 노드로 이동한다.

5번 노드에서 갈 수 있는 2번 노드는 이미 방문처리가 되어있기 때문에 탐색하지 않는다.

 

이후 1번 노드로 되돌아와서 마지막으로 남아있는 4번 노드를 방문한다.

 

따라서 1, 2, 3, 5, 4 노드 순서로 방문을 한다.

 

---

구현 (C++)

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[6];
bool visited[100001];

void dfs(int s)
{
    if (visited[s])
        return;
    visited[s] = true;
    cout << s << " ";
    for (auto u : adj[s])
    {
        dfs(u);
    }
}

int main()
{

    adj[1].push_back(2);
    adj[1].push_back(4);

    adj[2].push_back(1);
    adj[2].push_back(3);
    adj[2].push_back(5);

    adj[3].push_back(2);
    adj[3].push_back(5);

    adj[4].push_back(1);

    adj[5].push_back(2);
    adj[5].push_back(3);

    dfs(1);

    return 0;
}

 

처음에는 visited 배열의 모든 값이 false.

탐색 과정에서 s번 노드를 방문할 때 마다 visited[s]의 값은 true가 된다.