깊이 우선 탐색 (Depth-First Search)

1. 깊이 우선 탐색이란?

그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘.

깊이 우선 탐색은 재귀함수를 이용하기 때문에, 스택 오버 플로에 조심해야 한다.

후입선출의 특성을 가지므로 Stack이나 재귀함수 사용한다.

1. 시작 노드를 방문 처리하고, 인근 노드 하나를 방문한다.
2. 인근 노드의 인근 노드를 방문한다.
3. 더이상 방문할 노드가 없을때까지 반복한다.
4. 방문할 노드가 없으면 뒷 노드로 가서 방문하지 않은 노드가 있는지 확인한다.
   방문하지 않은 노드가 있으면 방문을 하고, 없으면 한번 더 뒷 노드로 간다.
5. 반복한다.

 

2. 사용처

특정 도시에서 다른 도시로 갈 수 있는지 확인할 경우.

전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 확인할 경우.

 

3. 그림

 

4. 코드

public class DepthFirstSearch {
    static private LinkedList<Integer> list[] = new LinkedList[5];

    public static void main(String[] args){
        for (int i = 0; i < list.length; i++) {
            list[i] = new LinkedList<>();
        }

        list[0].add(1);
        list[0].add(2);
        list[0].add(4);
        list[1].add(0);
        list[1].add(2);
        list[2].add(0);
        list[2].add(1);
        list[2].add(3);
        list[2].add(4);
        list[3].add(2);
        list[3].add(4);
        list[4].add(0);
        list[4].add(2);
        list[4].add(3);

        solution(0);
    }

    static boolean visited[] = new boolean[5];
    public static void solution(int start){
        visited[start] = true;

        System.out.print(start + " ");

        Iterator<Integer> iterator = list[start].listIterator();
        while (iterator.hasNext()){
            int near = iterator.next();

            if(!visited[near]) {
                solution(near);
            }
        }
    }
}