[Algorithm] 깊이우선탐색 DFS 에 대하여

# 그래프 순회 (Graph Traversal)
그래프의 모든 정점을 방문하는 것, 방문하는 방법.

그래프 순회

다음과 같은 그래프가 있을 때, 4개의 정점(노드, vertex)을 확인할 수 있을 것이다.

1, 2, 3, 4 총 4개의 정점을 모두 방문하는 것. 이를 그래프 순회라 부른다.

 

그래프 순회 알고리즘

그래프 순회 알고리즘에는 대표적으로 두가지가 있다.

 

1. 깊이우선탐색, DFS 

2. 너비우선탐색, BFS 

 

 

이번 포스트에서는 깊이우선탐색, DFS에 대해서 다룰 것이다.

---

DFS란 ?

Depth-First-Search. 깊이우선탐색. DFS. 

깊이를 우선적으로 고려하여 모든 정점을 순회하는 알고리즘.

더 이상 갈 수 있는 정점이 존재하지 않을 때까지 정점을 타고 내려간 후에, 갈림길까지 돌아가서 다시 순차적으로 탐색한다.

 

( 앞만 보고 가다가 억! 막혔네! 하면 다시 돌아오는 어떻게 보면 맹목적인 탐색법이다. )

 

DFS 동작과정

위의 예시는 http://visualgo.net 을 이용해 제작하였습니다.

VisuAlgo is free of charge for Computer Science community on earth. If you like VisuAlgo, the only payment that we ask of you is for you to tell the existence of VisuAlgo to other Computer Science students/instructors that you know =) via Facebook, Twitter, course webpage, blog review, email, etc.

If you are a data structure and algorithm student/instructor, you are allowed to use this website directly for your classes. If you take screen shots (videos) from this website, you can use the screen shots (videos) elsewhere as long as you cite the URL of this website (http://visualgo.net) and/or list of publications below as reference. However, you are NOT allowed to download VisuAlgo (client-side) files and host it on your own website as it is plagiarism. As of now, we do NOT allow other people to fork this project and create variants of VisuAlgo. Using the offline copy of (client-side) VisuAlgo for your personal usage is fine.

Note that VisuAlgo's online quiz component is by nature has heavy server-side component and there is no easy way to save the server-side scripts and databases locally. Currently, the general public can only use the 'training mode' to access these online quiz system. Currently the 'test mode' is a more controlled environment for using these randomly generated questions and automatic verification for a real examination in NUS. Other interested CS instructor should contact Steven if you want to try such 'test mode'.

List of Publications

This work has been presented briefly at the CLI Workshop at the ACM ICPC World Finals 2012 (Poland, Warsaw) and at the IOI Conference at IOI 2012 (Sirmione-Montichiari, Italy). You can click this link to read our 2012 paper about this system (it was not yet called VisuAlgo back in 2012).

This work is done mostly by my past students. The most recent final reports are here: Erin, Wang Zi, Rose, Ivan.

Bug Reports or Request for New Features

VisuAlgo is not a finished project. Dr Steven Halim is still actively improving VisuAlgo. If you are using VisuAlgo and spot a bug in any of our visualization page/online quiz tool or if you want to request for new features, please contact Dr Steven Halim. His contact is the concatenation of his name and add gmail dot com.

---

동작원리 

1.  하나의 정점(v)을 선택한다. ( a )
2.  정점(v) 에 인접한 모든 정점(i) 들에 대하여..........( b )
   1. 이미 방문한 정점이라면
      1.  (b) 로 이동하여 다른 정점(i) 을 탐색. 
   2. 처음 방문한 정점이라면
      1.  이 정점을 방문했음을 기록함.
      2.  이 정점을 v로하여 (a)로 이동. 

 

여기서 중요한 포인트는, '이 정점을 방문했음을 기록함' 이다.

DFS에서는 특정 정점의 방문 여부를 기록하고 체크하는 것이 가장 중요하다.

이 부분을 고려하지 않는다면 무한히 그래프를 돌고 돌 것이다.

 

그렇다면 실제로 DFS를 구현하려면 어떻게 해야할까? 

 

---

구현

기본적으로, 재귀 호출 방식으로 DFS를 구현한다. 

스택으로 구현하는 방식도 있다. 재귀 호출 자체의 실행 context 자체가 스택을 사용하니 어찌보면 당연하다.

이 포스팅에서는 재귀 호출 방식으로 간단한 dfs 함수를 구현해 볼 것이다.

 

위에서 말했듯이, 이 정점을 방문했음을 알기위해서는 이 정보를 기록하는 추가 공간이 필요하다.

통상적으로 visit이라는 이름으로 많이들 사용한다.

 

int mat[5][5]={};

// 간선 추가
mat[1][2]=mat[2][1]=1;
mat[1][3]=mat[3][1]=1;
mat[2][3]=mat[3][2]=1;
mat[3][4]=mat[4][3]=1;

위와 같이 4개의 정점이 있고 다음과 같이 양방향의 간선이 추가되었다고 해보자.

 

int visit[5]={};
void dfs(int v){
	visit[v] = 1;
	for(int i=1;i<=4;i++){
    	if(mat[v][i] && !visit[i]) dfs(i);
    }
}

4개의 정점에 대한 1차원 visit 배열을 선언했다.

 

dfs가 호출되면 인자로 받은 정점 v에 방문했음을 기록한다. 

그리고 존재하는 4개의 정점 중에서 다음에 방문할 정점을 찾는다.

 

mat[v][i] : 현재 정점 v -> 정점 i 간의 간선이 존재한다.

!visit[i] : 정점 i 에 방문한 적이 없다.

 

위의 두 조건을 만족하는 정점 i에 대하여 dfs를 재귀호출하면 된다.

---

코드로 보니 생각보다 간단해보인다.

하지만 이는 기본적인 dfs의 뼈대와 같은 느낌이다.

실제로 응용해서 사용하려고하면 굉장히...어렵다.

 

그래도 뭘 하든 기초가 가장 중요하다고 했다. 

> www.acmicpc.net/problem/1260

가장 기초적인 BFS와 DFS를 구현하는 문제이다. 한 번 풀어보길 추천한다. ( DFS를 처음 접하는 분이라면 )

 

---

특징

1. 최단 경로를 보장하지 않는다. 
2.  시간복잡도
   1. 인접리스트: O(v+e) // v : number of vertex,  e : number of edge
   2. 인접행렬 : O(v^2)