"깊이우선탐색(Depth First Search) 이란 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. "
그래프 탐색이란 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다. 예를 들어 특정도시에서 다른 도시로 갈 수 있는지, 전자회로에서 특정 단자와 단자가 서로 연결되어 있는지를 탐색하는 알고리즘이다.
또 다른 그래프 탐색 방법으로는 너비우선탐색이있다. 해당 알고리즘에 대한 포스팅은 "너비우선탐색 포스팅"에서 확인할 수 있다.
깊이우선탐색이기 때문에 한 방향으로 인접한 노드가 없을 때까지 (가장 깊은 노드까지) 탐색한 뒤 다른 방향으로 탐색을 하는 방식이다.
다음과 같은 순서를 따른다.
( 사진 출처: heejeong Kwon님의 기술블로그 )
위에서 설명한 3단계의 알고리즘으로 사진속의 과정을 설명하자면,
- 인접행렬
- 인접리스트
예를 들어보자.
위와 같은 그래프를 구현할 때 다음과 같이 인접행렬과 인접리스트로 구현할 수 있다.
인접행렬은 이차원배열, 인접리스트는 링크드리스트 배열, 어레이리스트 배열, 어레이리스트를 저장하는 어레이리스트 등과 같은 방식으로 구현할 수 있다.
인접행렬로 구현할 때 필요한 구조
static void dfs(int node) {
DFSisVisited[node] = true; //노드방문여부를 true로 저장
DFSvisitArr.add(node); //방문한 노드를 순서대로 저장하는 리스트에 해당노드 추가
for( int i = 1 ; i <= nodeNum ; i++ ) {
//for문에서 backtracking을 수행한다.
if(graph[node][i] == 1 && DFSisVisited[i] == false) {
//인접, 방문된적X 를 만족하는 노드를 방문
dfs(i);
}
}
}
인접리스트로 구현할 때 필요한 구조
static void dfs(int node) {
DFSisVisited[node] = true; //노드방문여부를 true로 저장
DFSvisitArr.add(node); //방문한 노드를 순서대로 저장하는 리스트에 해당노드 추가
for( int i = 0 ; i < graph[node].size() ; i++ ) {
//for문에서 backtracking을 수행
int adjNode = graph[node].get(i);
if(DFSisVisited[adjNode] == false) {
//인접, 방문된적 없는 노드를 방문
//adjNode에는 인접노드만 저장되므로 인접조건O
dfs(adjNode);
}
}
}