[알고리즘]C++ DFS구현하기

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

말 그대로 탐색할 수 있는 만큼 깊게 들어가 순차적으로 탐색하는 방법이다.

아래와 같은 그래프 형태에서 

한 시작점 노드(v)에서 연결된 모든 노드(w1,w2,w3)들 중 w1부터 탐색하는데 

한번 w1를 탐색하면 해당노드(w1)에 연결된 노드들을 우선적으로 찾아 계속 연결된 노드를 탐색한다.

w1의 탐색이 완료되면 다시 v기준으로 w2를 탐색하고 이를 반복한다.

이를 소스로 구현하면 다음과 같다.

#include<iostream>
using namespace std;
int maps[10][10];
int visited[10]={0};
int num;
void init(){
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++)
            maps[i][j] = 0;
}
 
void dfs(int v)
{
    cout<<v<<endl;
    visited[v] = 0;
    for(int i = 0; i <= num; i++)
    {
        if(maps[v][i] && visited[i]) 
            dfs(i);
    }
}
 
int main(void)
{
    int v1,v2;
    init();
    cin>>num;
    for(int i=0;i<num;i++)
    {
        cin>>v1>>v2;
        maps[v1][v2] = maps[v2][v1] = 1;
        visited[v1] = visited[v2] = 1;
    }
    dfs(1);
 
    return 0;
}

우선 8개의 노드가 있다고 가정하고,

연결된 노드를 쌍으로 입력받는다.(총 10개의 간선)

maps라는 2차원 배열을 통해 인접한 노드끼리 1을 입력해주고,

방문여부를 확인하기 위해 visited 배열에 1을 입력해준다.

dfs함수에 들어가면 해당 노드를 출력하고 방문했음을 알리기 위해

visited배열에 0을 입력한다.(보통 방문했음을 1로 표시함)

다른 모든 노드를 대상으로 1.인접해있고 2.방문하지 않았으면

그 노드를 기준으로 다시 bfs함수를 호출한다.

오른쪽은 노드를 생성한 것이고 이를 아래 그래프로 나타내었다.

1 2 4 8 5 6 3 7 순서로 잘 탐색함을 알 수 있다.

그래프 출처: samsungexpertacadmey