[C++][DFS(깊이 우선탐색) 알고리즘]

그래프의 탐색이란

루트부터 아래 노드들 까지 모든 정점을 방문하는 것이다.

깊이 우선 탐색(DFS)이란?

깊이 우선 탐색은 트리나 그래프에서 한 루트로 최대한 깊숙이 들어가서 탐색한 후 다시 돌아와 다음 루트도 깊이 탐색하는 방법이다.

일반적으로 재귀 호출을 사용하여 구현한다. 단순 검색 속도는 BFS보다 느리다.

장점

1. 목표 노드가 깊이 있으면 빨리 구할 수 있다.

2. 매번 기억하는 노드가 하나이므로 저장 공간의 수요가 적다.

단점

1. 목표노드가 없는 경로의 깊이 빠질 수 있다.-> 시간이 많이 걸릴 수도 있다.

알고리즘 설명

그림과 같이 루트가 1인 트리가 있다.

루트가 1이므로 루트 1에 대하여 DFS를 하면 최대 노드 3까지 내려가게 된다.

다음 루트는 이제 노드 2가 되어서 노드 2에 대하여 DFS를 하게 되면 다음과 같다. 

이제 다시 노드 1이 루트가 되어서 오른쪽 서브 트리를 DFS 하게 된다.

이제 다음 루트는 노드 4가 되어서 DFS하게 된다.

이렇게 전체 노드를 탐색할 수 있게 된다.

 코드로 나타내면 다음과 같다.

코드

#include <iostream>
#include <vector>
using namespace std;
int N,M; // N은 노드의 갯수 M은 간선의 갯수 
vector <int> adj[10];
bool visit[10] = {false};
void DFS(int node){
    cout << node << "\n";
    visit[node] = true; //현재 방문했으므로 true로 체크 해준다.
    // 현재 방문한 노드가 연결되어 있는 노드를 전부 탐색한다.
    for(int i = 0;i<adj[node].size();i++){
        int next_node = adj[node][i]; //현재노드의 연결된 노드
        if(visit[next_node] == true){continue;} //이미 방문한 노드면 방문하지 않는다.
        DFS(next_node); //다음노드를 탐색한다.
    }
}
int main(void){
    // 입력값 8 7
    cin >> N >> M;
    for(int i = 0;i<M;i++){
        int a,b;
        /* 인접리스트로 표현한다.
        입력 값
        1 2
        1 4
        2 3
        2 5
        5 7
        4 8
        4 6
        */
        // 인접 리스트 생성
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    DFS(1); //루트를 시작으로 DFS시작
}

결과값

1

2

3

5

7

4

8

6

 

 

DFS 탐색 완료!!