DFS (Depth-First Search)

들어가기전, 스택 (Stack)

https://devfunny.tistory.com/708

스택 (Stack)

 

 

DFS

- 깊이 우선 탐색

- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

- 스택 또는 재귀함수를 사용한다.

 

[수행 과정]
1) 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다.
    방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3) 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

 

 

DFS 동작 예시

0) 아래 그래프를 번호가 낮은 인접 노드부터 방문한다.

https://freedeveloper.tistory.com/273?category=888096

 

1) 노드 '1' 방문

https://freedeveloper.tistory.com/273?category=888096

 

2) 노드 '2' 방문

- 방문 노드 '1'의 인접 노드인 '2', '3', '8' 중 가장 작은 노드의 '2'를 방문한다.

https://freedeveloper.tistory.com/273?category=888096

 

3) 노드 '7' 방문

- 노드 '2'에 방문하지 않은 인접 노드 '7'를 방문한다.

https://freedeveloper.tistory.com/273?category=888096

 

4) 노드 '6' 방문

- 노드 '7'의 인접노드 '6', '8' 중에서 가장 작은 '6' 노드를 방문한다.

https://freedeveloper.tistory.com/273?category=888096

 

5) 노드 '6' 을 꺼낸다.

- 스택의 최상단 노드인 '6'에 방문하지 않은 인접노드가 없다.

https://freedeveloper.tistory.com/273?category=888096

 

6) 노드 '8' 방문

- 스택의 최상단 노드인 '7'의 인접 노드이면서, 방문하지 않은 노드 '8'을 방문한다.

https://freedeveloper.tistory.com/273?category=888096

 

7) 위 과정을 모든 노드를 방문할때까지 반복한다.

결과

https://freedeveloper.tistory.com/273?category=888096

 

 

 

DFS 구현코드 (인접행렬)

import java.util.ArrayList;

/**
 * DFS
 */
public class M7_DFS {

    // 방문 여부
    public static boolean[] visited = new boolean[9];

    // 그래프
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    // DFS 함수 정의
    public static void dfs(int x) {
        // 현재 노드를 방문 처리
        visited[x] = true;
        System.out.println(x + " ");

        // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for (int i = 0; i < graph.get(x).size(); i++) {
            int y = graph.get(x).get(i);

            if (!visited[y]) { // 방문하지 않았을 경우 방문
                dfs(y);
            }
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화
        for (int i = 0; i < 9; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 노드 1에 연결된 노드 정보 저장
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);

        // 노드 2에 연결된 노드 정보 저장
        graph.get(2).add(1);
        graph.get(2).add(7);

        // 노드 3에 연결된 노드 정보 저장
        graph.get(3).add(1);
        graph.get(3).add(4);
        graph.get(3).add(5);

        // 노드 4에 연결된 노드 정보 저장
        graph.get(4).add(3);
        graph.get(4).add(5);

        // 노드 5에 연결된 노드 정보 저장
        graph.get(5).add(3);
        graph.get(5).add(4);

        // 노드 6에 연결된 노드 정보 저장
        graph.get(6).add(7);

        // 노드 7에 연결된 노드 정보 저장
        graph.get(7).add(2);
        graph.get(7).add(6);
        graph.get(7).add(8);

        // 노드 8에 연결된 노드 정보 저장
        graph.get(8).add(1);
        graph.get(8).add(7);

        dfs(1);
    }
}