DFS(Depth-First-Search) 알고리즘

DFS(Depth-First-Search) Algorithm

DFS Algorithm

- 그래프나 트리같은 자료구조에서 탐색을 할 때 사용하는 알고리즘 중 하나

- DFS는 구현 방식이 여러가지 있고 각각으 시간 복잡도는 다름

- 하나의 정점부터 가장 깊이가 깊은 곳까지 탐색하며 방문하지 않은 모든 정점들을 탐색함

 

DFS Complexity

- 인접 리스트를 사용해 그래프를 구현하는 경우와 인접 행렬을 이용해 구현하는 경우 시간복잡도가 다름

1) 인접 리스트

- 한 정점에서 방문할 수 있는 정점을 간선 기준으로 탐색할 수 있기 때문에 O(V+E)의 시간 복잡도를 갖는다.

2) 인접 행렬

- 방문할 정점을 찾을 때 연결된 모든 정점을 순회하며 이어져 있는지 체크를 해야 되기 때문에 O(V^2)의 시간 복잡도를 갖는다.

V : 정점의 개수, E : 간선의 개수

DFS Process

- 방문하지 않은 정점부터 시작함

- 방문할 정점이 이미 방문했던 정점이라면 탐색하지 않고 다른 정점들을 탐색함

- 모든 정점을 탐색할 경우 DFS를 종료함

Example) DFS 과정

- 단방향 그래프 DFS

- 1번 노드에서 모든 정점으로 갈 수 있는 경로가 있다고 가정

먼저 방문 여부를 확인할 Visit배열을 모두 0(방문하지 않음)으로 초기화.

초기화한 후 1번 정점부터 탐색을 시작함

1번 정점으로 시작하며 visit배열의 값을 1(방문함)로 바꿔주고 1번 노드에서 방문할 수 있는 정점을 찾음.(2,3)

2번 정점의 Visit값을 확인하고 방문하지 않았기 때문에 다음 정점을 2번으로 선택한다. 

2번 정점을 방문하며 Visit배열의 값을 바꿔주고 연결된 다음 정점을 확인한다.

4,5번 정점이 연결되어 있으므로 4번으로 넘어간다.

4번 정점의 Visit값을 1로 바꿔주고 다음 정점을 찾는다. 7번 정점으로의 경로밖에 없기 때문에 7번 정점으로 간다.

7번 정점의 Visit값을 1로 바꿔주고 다음으로 방문할 정점을 찾는다. 7번 정점에서 갈 수 있는 경로는 5번 정점으로의 경로 밖에 없기 때문에 5번을 선택한다.

5번 정점의 Visit값을 1로 바꿔주고 다음으로 방문할 정점을 찾는다. 5번 정점에서 갈 수 있는 경로는 6번 정점으로 가는 경로가 있다. 6번 정점을 탐색한다.

6번 정점의 Visit값을 1로 바꿔주고 갈 수 있는 경로를 찾는다. 6번 정점에서는 7번 정점으로 갈 수 있으므로 7번 정점을 선택한다.

7번 정점으로 가야하지만 7번 정점은 앞 선 탐색에서 이미 탐색했던 정점이다. Visit 배열의 값이 1로 되어있으므로 탐색을 종료한다. 이 후에 위 경로에서 탐색할 수 있는 정점들은 끝났기 때문에 왔던 경로로 다시 돌아간다. 이러한 것을 구현하기 위해 재귀로 구현한다.

왔던 경로대로 돌아가던 중 2번 정점에서는 5번 정점으로 가는 경로가 하나 더 있다.

하지만 5번 정점은 이미 방문했던 정점이기 때문에 탐색하지 않고 다시 돌아간다.

이제 원래의 시작 정점이였던 1번 정점으로 돌아왔다. 1번 정점에서 3번 정점으로 가는 경로를 아직 탐색하지 않았기 때문에 3번 정점을 선택한다.

3번 정점의 Visit값을 1로 바꿔주고 3번 정점에서 갈 수 있는 경로를 찾는다. 5번 정점으로 갈 수 있기 때문에 5번 정점을 선택한다.

하지만 5번 정점은 아까전에 이미 방문했기 때문에 재 방문하지 않고 재귀로 다시 돌아간다.

이러한 방식으로 모든 정점들을 탐색한 후 종료한다.

실제로는  모든 정점들이 연결되지 않은 그래프일 수 있으므로 이러한 것을 각 정점별로 확인해줘야한다. 위 예제에서는 1번 정점에서 모든 정점을 갈 수 있는 그래프로 설명하여 1번 정점만 탐색하였다.

양방향 그래프도 위 방법과 마찬가지로 탐색을 한다.

DFS Algorithm Source Code

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
 
/*
    vertex_count : Vertex 개수
    edge_count : Edge 개수
    visit : 방문한 Node 확인
    vectex[x][y] : x->y로 의 경로
*/
 
bool visit[8] = { 0, };
//bool vertex[8][8] =  { 0, };    // 각 정점에서 모든 정점까지의
                                // 경로를 확인하는 인접행렬 방식
vector <int> vertex[8];
int vertex_count, edge_count;
int from, to;
 
void DFS(int node) {
    visit[node] = 1;    // 방문하면서 visit배열의 값을 바꿔준다.
    cout << node << " ";
    int available_path_size = vertex[node].size();    // 현 정점에서의 경로 개수
    
    for (int i = 0; i < available_path_size; i++) {
        int next_vertex = vertex[node][i];    // 갈 수 있는 경로의 vertex number
        if (visit[next_vertex] == 0) {        // 방문하지 않은 정점이라면
            DFS(next_vertex);
        }
    }
    return;
}
 
int main()
{
    cin >> vertex_count >>  edge_count;
    
    for (int i = 0; i < edge_count; i++) {    // Edge의 개수만큼 연결관계를 입력받음
        cin >> from >> to;
        // vertex[from][to] = 1;        // from->to로 가는 경로 (인접행렬)
        vertex[from].push_back(to);        // from->to로 가는 경로 (인접리스트)
    }
    memset(visit, 0, sizeof(visit));    // 방문 여부를 확인할 visit배열을 모두 0(false)로 초기화
    
    /*    실제로는 모두 연결된 그래프가 아니거나 경로가 없는 경우 탐색이 안되는
        정점이 생길 수 있으므로 모든 정점에서 해봐야한다.

    for (int i= 1; i <= vertex_count; i++) {
        if (visit[i] == 0) {
            DFS(i);
        }
    }
    */
    cout << "Visit Order : ";
    DFS(1); // 1번 정점에서 모두 갈 수 있는 예제를 사용하기 때문에 이렇게 사용했다.
    cout << endl;
    return 0;
}
 
/*
    Input case:
    7 9
    1 2
    1 3
    2 4
    2 5
    4 7
    5 6
    7 5
    6 7
    3 5
*/

vector를 사용하여 인접 리스트 방식으로 구현.

단방향 그래프로 구현했고 입력으로 1번 정점에서 모든 정점으로 갈 수 있는 경로가 있는 경우의 case를 넣어줌

위 DFS Process에서 설명한 방식대로 진행하고 방문한 정점 순서대로 출력함