DFS 깊이 우선 탐색 알고리즘

By Jimmyberg
algorithm dfs 알고리즘 깊이우선탐색

깊이 우선 탐색 알고리즘

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

특징

  • 재귀 함수로 구현
  • Stack 자료구조 활용
  • 시간 복잡도 : O(V + E)

시간 복잡도 표현 방법

  • V : 노드 수
  • E : 에지 수

구현 순서

1. DFS 를 시작할 노드를 정한 후 사용할 자료구조 초기화하기

  • 인접 리스트로 그래프 표현
node 1 : 2, 3
node 2 : 5, 6
node 3 : 4
node 4 : 6
node 5 : x
node 6 : x
  • 방문 배열 체크
check_arr : {T, F, F, F, F, F}
  • Stack 자료구조에 시작점 더하기
|   |
|   |
|   |
| 1 |

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드 다시 스택에 삽입하기

  • 스택에서 노드 pop 하여 해당 노드의 인접 노드 스택에 저장
    • node 1 를 꺼낸 후, 인접 노드 node 2, 3 을 스택에 저장
|   |
|   |
| 3 |
| 2 |
  • 방문 배열 체크
check_arr : {T, T, T, F, F, F}

3. 스택 자료구제 값이 없을 때까지 반복하기

  • 1 ~ 2 번 순서를 스택 자료구조에 값이 없을 때까지 반복한다. 대신, 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않도록 한다.
    • node 3 를 꺼내면, 인접 노드 node 4 를 스택에 저장 및 방문 배열 체크
    • node 4 를 꺼내면, 인접 노드 node 6 를 스택에 저장 및 방문 배열 체크
    • node 6 를 꺼내면, 인접 노드가 없기 때문에 스택 저장 없음
    • node 2 를 꺼내면, 인접 노드 node 5, 6 이지만, 이미 node 6 은 방문했기 때문에 node 5 만 스택에 저장 및 방문 배열 체크

DFS 실행 순서

node 1 : 2, 3
node 2 : 5, 6
node 3 : 4
node 4 : 6
node 5 : x
node 6 : x

실행 순서 : 1 -> 3 -> 4 -> 6 -> 2 -> 5

구현

/**
 * [Sample]
 * 5 5 3  // node 수, edge 수, 시작점
 * 5 4
 * 5 2
 * 1 2
 * 3 4
 * 3 1
 *
 * // 실행 순서
 * 3 1 2 5 4
 *
 * // 조건
 * 인접 노드가 여러 개일 경우, 번호가 작은 것부터 먼저 방문한다.
 */
public class DFS {
    static List<String> result;
    static List<List<Integer>> graph;
    static boolean[] visited;

    public static void main(String[] args) {
        System.out.println("============ START =============");
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int E = sc.nextInt();
        int start = sc.nextInt();

        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }
        visited = new boolean[N + 1];

        for (int i = 0; i < E; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        for (List<Integer> child : graph) {
            child.sort(Comparator.comparingInt(o -> o));
        }

        dfs(start);

        System.out.println("dfs result : " + String.join(" ", result));
    }

    static void dfs(int k) {
        if (visited[k]) return;

        visited[k] = true;
        result.add(String.valueOf(k));

        for (int i : graph.get(k)) {
            // 재귀 호출 방식으로 dfs 수행
            dfs(i);
        }
    }
}

출처