[2][그래프 이론] - 깊이 우선 탐색 DFS (Depth-First Search)

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

깊이 우선 탐색(이하 DFS)은 하나의 정점에서 시작해서 그래프를 탐색 하는 방법중 하나로 한 정점에서 갈수있는 정점을 방문하고 해당 정점에서 갈수 있는곳을 계속해서 방문하여 더이상 방문할 정점이 없을때까지 방문하는 방법이다.

 

쉽게생각해서 미로탈출 게임을 할때 만약 세가지 갈림길이 나왔을 때, 셋중 하나를 골라서 끝까지 진행해본후 막혀있다면 다시 원점으로 돌아와 다른 길로 가는 것과 같이 생각하면 될것이다.

 

다음과 같은 방향이 없는 그래프로 생각해보자.

 

 

0번 정점에서 시작해서 DFS를 수행하는 과정은 다음과 같다.

 

 

이번 DFS에서는 현재 정점에서 갈 수 있는 정점들 중 가장 번호가 낮은 정점부터 방문한다고 가정하자.

 

0번 정점에서 처음에 갈수 있는 정점은 1과 9번이다. 

 

이중 1번을 먼저 방문한다.

 

1번에서는 0,2,5,7 번을 방문할수 있는데 이중 0번은 이미 방문 했으므로 제외하고 가장 낮은 번호인 2번부터 방문하고

 

이같은 과정을 계속 반복한다.

 

순환하는 과정을 보아하니 재귀함수로 해결할수 있을 것 같다.

 

이미 방문한 곳을 제외하고 방문하는 과정만 잘 설계하면 될것이다.

 

vector<vector<int> > graph;

int visited[10]; // 0 - 미방문 / 1 - 방문

void dfs(int v){
    cout << "visit " << v << endl;
    visited[v] = 1;
    for(int i=0; i<graph[v].size(); i++){
        if(visited[graph[v][i]] == 0){
            dfs(graph[v][i]);
        }
    }
}

해당 코드는 c++로 설계되었으며 그래프 상태는 2중 벡터를 사용하였다.

 

그리고 방문 상태를 체크하기 위해 1차원 배열을 사용하여 방문 이력을 기록하였고

 

현재 정점에서 갈수 있는 정점들 중 아직 방문을 하지 않은( visited[i] == 0 인 ) 정점들에 대해 재귀로 dfs(i) 를 수행하였다. 

 

 

 

 

 

DFS 를 c++로 구현한 전체 코드

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int> > graph;

int visited[10]; // 0 - 미방문 / 1 - 방문

void dfs(int v){
    cout << "visit " << v << endl;
    visited[v] = 1;
    for(int i=0; i<graph[v].size(); i++){
        if(visited[graph[v][i]] == 0){
            dfs(graph[v][i]);
        }
    }
}

int main(){
    for(int i=0;i<10;i++){
        graph.push_back(vector<int>());
        visited[i] = 0;
    }
    graph[0].push_back(1);
    graph[0].push_back(9);
    graph[1].push_back(0);
    graph[1].push_back(2);
    graph[1].push_back(7);
    graph[2].push_back(1);
    graph[2].push_back(3);
    graph[2].push_back(4);
    graph[2].push_back(5);
    graph[3].push_back(2);
    graph[4].push_back(2);
    graph[5].push_back(2);
    graph[5].push_back(6);
    graph[5].push_back(1);
    graph[7].push_back(1);
    graph[7].push_back(8);
    graph[7].push_back(9);
    graph[8].push_back(7);
    graph[9].push_back(0);
    graph[9].push_back(7);

    dfs(0);
}

 

최종적으로 다음과 같이 출력이 된다.