깊이우선탐색(DFS)
깊이우선탐색(Depth First Search)
깊이우선탐색은 탐색을 함에 있어서 보다 깊은것을 우선적으로 하여 탐색하는 알고리즘이다.
깊이우선탐색은 기본적으로 전체 노드를 맹목적으로 탐색하고자 할 때 사용하며
스택(Stack) 자료구조에 기초한다.
빠르게 모든 경우의 수를 탐색하고자 할 때 쉽게 사용할 수 있으며
다음과 같은 알고리즘에 따라 구현할 수 있다.
탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.
스택의 최상단 노드에게 방문하지 않은 인접노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리를 한다.
방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.
위 과정을 더이상 수행할 수 없을 때 까지 반복한다.
깊이우선탐색 수행과정
이러한 형태의 그래프를 탐색하며 1부터 출발한다고 가정한다.
1부터 출발하면 1에서 연결된 노드 중 방문하지 않은 2를 방문하고 2에서도 방문하지 않은 7을 방문한다.
7에서는 6을 방문하는데 6의 경우는 연결된 노드가 없기 때문에 스택에서 제거하고 7에 연결된 8을 방문한다.
8은 1과 연결되어있으며 방문하지 않은 인접노드가 없기 때문에 8, 7, 2를 스택에서 제거한다.
1에서 방문하지 않은 인접노드인 3을 방문하고 3은 4를 4는 5를 방문한 뒤 더이상 방문할 인접노드가 없기에
스택을 비워준다.
스택 형태로 보면 다음과 같다.
| 1 | 2 |
| 1 | 2 | 7 |
| 1 | 2 | 7 | 6 |
| 1 | 2 | 7 | 8 |
| 1 | 3 |
| 1 | 3 | 4 |
| 1 | 3 | 4 | 5 |
방문순서를 정리해보면 1 2 7 6 8 3 4 5순서이다.
스택자료구조에 기초한다는 점에서 구현이 간단하지만 실제로는 스택을 쓰지않아도 재귀함수를 이용하면 기본적으로
스택과 비슷하게 동작한다는 점에서 재귀함수로 간단히 구현할 수 있으며 탐색을 수행함에 있어서 O(N)의 시간이
소요되는 전수탐색 알고리즘이다.
import java.io.*;
import java.util.*;
public class Graph{
private int V;//노드의 개수
private LinkedList<Integer> adj[];//인접리스트
Graph(int v){
V = v;
adj = new LinkedList[v];
for(int i = 0; i < v; ++i){//인접리스트 초기화
adj[i] = new LinkedList();
}
}
void addEdge(int v, int w){
adj[v].add(w);
/*
연결된 리스트 확인
for(int i = 0; i < adj.length; i++){
System.out.println("adj["+i+"] : "+adj[i]);
}
*/
}
void DFSUtil(int v, boolean visited[]){
//현재 노드를 방문한것으로 표시하고 값을 출력.
visited[v] = true;
System.out.print(v + " ");
//방문한 노드와 인접한 모든 노드를 가져온다.
Iterator<Integer> i = adj[v].listInteger();
while(i.hasNext()){
int n = i.next();
/*
다음값인 n의 값 확인
System.out.println("i.next : "+n);
*/
//방문하지 않은 노드면 해당 노드를 시작 노드로 다시 DFSUtil 호출
if(!visited[n]){
DFSUtil(n, visited);
}
}
}
void DFS(int v){
//노드의 방문여부 판단 (초기값 : false)
boolean visited[] = new boolean[V];
//v를 시작노드로 DFSUtil 순환 호출
DFSUtil(v, visited);
}
/*
비 연결형 그래프일 경우
void DFS(){
//노드의 방문여부 판단
boolean visited[] = new boolean[V];
//모든 정점을 하나씩 방문
for(int i = 0; i < V; ++i){
if(visited[i] == false){
DFSUtil(i, visited);
}
}
}*/
public static void main(String[] args){
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.DFS(2);
//DFS(); 비연결형그래프
}
}강의에서 본 C예제코드는 이해가 많이 떨어져서 java코드로 예제를 찾아 학습했다.
위 코드의 결과값은 2 0 1 3이 출력된다.
스택을 이용한 구현이 아닌 재귀함수를 이용한 구현이다.
addEdge는 노드를 연결해주는 것인데 다 연결되고나면
adj[0] = [1, 2]
adj[1] = [2]
adj[2] = [0, 3]
adj[3] = [3]
이런 형태가 된다.
그림으로 본다면
이렇게 연결된 그래프형태다.
연결까지 다 처리되고 나면 DFS로 시작노드를 넘겨주면서 처리하게 되는데 visited[]는 boolean형태로 V만큼의 크기를
설정함으로써 adj배열과 같은 크기로 설정해준다.
이때 모든 기본값은 false가 된다.
DFSUtil에서는 v와 visited를 넘겨 처리해준다.
처음 넘겨주는 노드는 2로 임의로 정한건데 visited[2] = true를 해줌으로써 2번 노드는 방문했다는것을 확인할 수
있도록 한다.
방문한 노드는 우선적으로 출력을 해주고 Iterator로 방문한 노드와 인접한 모든 노드를 가져온다.
이 경우 adj[2] = [0, 3]이기 때문에 0과 3을 가져온다.
연결되어있는 다음노드가 존재한다면 반복문을 실행하고 n에 next값을 넣어준다.
그럼 n은 0이 되고 visited[0]은 아직 방문하지 않은 false상태이기 때문에 DFSUtil함수를 호출하게 된다.
이렇게 계속 재귀적으로 반복하며 모든 노드를 방문하도록 수행한다.
레퍼런스
● 패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직