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

깊이 우선 탐색(DFS)은 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법이다. 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있는 경우 그 간선을 무조건 따라가는 것이다. 더이상 갈 곳이 없는 막힌 정점에 도달하면 마지막에 따라왔던 간선을 따라 다시 뒤로 돌아간다.

 

깊이 우선 탐색이 이루어 지는 과정

정점 S에서 탐색을 시작하면 처음으로 간선 (S, A)를 탐색하게 된다. A를 아직 탐색한 적이 없으므로 A로 움직인다. 같은 원리로 B, C로 가는 경로를 찾으면 갈 길이 없음을 알 수 있다. A는 이미 방문하였으므로 (A, C)간선을 따라갈 수는 없기 때문이다. 따라서 마지막으로 따라온 간선인 (B, C)를 따라 다시 이동하여 B에서 다시 방문하지 않은 정점이 있는지 확인하여 방문하지 않은 정점 D로 이동하고 D에서 다시 이동할 곳이 없으니 B로 다시 돌아온다. E, F도 이렇게 방문하고 나면 다시 되돌아가 A로 돌아오게 되고 나머지 방문하지 않은 정점에 대해서도 동일하게 수행하며 DFS탐색을 진행한다.

DFS에서 가장 중요한 것은 더 따라갈 간선이 없을 경우 이전으로 돌아가야 한다는 것이다. 따라서 재귀호출로 구현하는 것이 좋다.

 

구현

vector<vector<int>> adj;	//그래프의 인접 리스트 표현
vector<bool> visited;	//각 정점의 방문 여부

//깊이 우선 탐색 구현
void dfs(int here){
	visited[here] = true;
    
    //모든 인접 정점 순회
    for(int i=0; i<adj[here].size(); i++){
    	int there = adj[here][i];
        
        //아직 방문한 적 없다면 방문
        if(!visited[there])
        	dfs(there);
        }
    }
    //더이상 방문할 정점이 없으므로 재귀호출 종료 후 이전 정점으로
}

//모든 정점 방문
void dfsAll(){
	//visited를 모두 false로 초기화
    visited = vector<bool>(adj.size(), false);
    
    //모든 정점을 순회하며 아직 방문하지 않은 경우 방문
    for(int i=0; i<adj.size(); i++){
    	if(!visited[i])
        	dfs(i);
    }
}

모든 정점이 간선을 통해 연결되어있다는 보장이 없기 때문에 dfs()만으로는 모든 정점을 탐색할 수 없어, dfsAll()함수가 필요하다.

 

 

 

출처: 알고리즘 문제해결 전략(구종만)