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

깊이 우선 탐색이란?

정점(V ; Vertex) 와 간선 (E ; Edge)로 구성된 그래프 (G ;Graph) 가 존재할 때 G(V,E)

임의의 정점 A를 시작으로 깊이순(재귀적)으로 그래프를 탐색하는 알고리즘이다.

 

예를 들어 아래와 같이 구성된 그래프 G(V,E) 가 있다고 하자.

 

 

 

 

5번 정점(V) 부터 시작해서 인접한 정점 중 작은 번호를 가진 정점부터 탐색을 한다고 하면,

5보다 작은 정점인 4번 정점을 탐색하고 1번 정점을 탐색하게 된다.

그리고 더 이상 탐색할 정점이 없다.

탐색할 위치가 남아있는 정점으로 다시 돌아간다. 그러면 5번정점으로 돌아가게 된다.

5번 탐색 -> 4번 -> 1번

그러면 이후 6번 정점을 탐색하게 되고 3번 정점을 탐색하게 된다.

그리고 더이상 탐색할 정점이 없다.

탐색할 위치가 남아있는 정점인 6번 정점에서 다시 탐색한다.

5번 -> 6번 -> 3번

6번 정점에서 9번정점을 탐색할 수 있으므로 9번정점을 탐색한다.

 

9번을 탐색한 이후 탐색할 수 있는 정점이 없으므로 탐색이 가능한 정점으로 돌아간다.

그러면 6번정점에 인접한 정점은 모두 탐색하였으므로 5번정점으로 돌아간다.

이후 5번정점으로 돌아가서 8번정점 그리고 7번정점을 탐색할 수 있고, 더 이상 탐색할 정점이 없으므로 탐색을 종료한다.

5->8->7

 

탐색의 순서는 5번 -> 4번 -> 1번 -> 6번 -> 3번 -> 9번 -> 8번 -> 7번 순이 된다.

코드로 작성해보면 아래와 같을 수 있으며, 결과또한 위의 탐색 순서와 동일하게 나오는 것을 볼 수 있다.

 

입력으로는 정점 (u) 와 정점 (v) 이 주어진다.

u v 로 입력하면 간선이 정점u와 정점v 사이에 존재하는 것을 의미함.

예제 입력으로는 총 7개 간선이 존재하는 것으로 위 그림과 동일한 예시이다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
 
typedef vector<int> VI;
 
VI edge[10];
bool vis_vertex[9];
 
void DFS(int node){
    vis_vertex[node] = true;
    printf("visit vertex %d\n", node);
    for(auto iter = edge[node].begin() ; iter != edge[node].end() ; iter++){
        int there = *iter;
        if(!vis_vertex[there]){
            DFS(there);
        }
    }
    return ;
}
int main(){
    /*
        input data ; 간선 정보
        1 4
        4 5
        5 6
        5 8
        7 8
        6 9
        3 6
    */
    for(int i = 0 ; i < 7 ; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        edge[u].push_back(v);
        edge[v].push_back(u);
        sort(edge[u].begin(), edge[u].end());
        sort(edge[v].begin(), edge[v].end());
    }
    DFS(5);
    
    return 0;
}
/*
output
Success    time: 0 memory: 15240 signal:0
visit vertex 5
visit vertex 4
visit vertex 1
visit vertex 6
visit vertex 3
visit vertex 9
visit vertex 8
visit vertex 7
*/

 

 

 

0123456