DFS ( Depth First Search )

DFS, 깊이 우선 탐색이라고도 불리는 탐색 방법이다.
DFS는 그래프를 탐색하는 대표적인 알고리즘 중 하나이다.

시작 정점에서 다음 분기로 넘어가기 전,
해당 분기를 완벽하게 탐색하는 방법을 통해 그래프의 모든 정점을 탐색한다.

DFS는 재귀함수를 통해 구현한다.

DFS를 통해 그래프를 탐색하는 방법은 다음과 같다.

• 1. 정점을 N, 간선을 E로 변수 선언
• 2. 2차원 배열 Graph[][] 를 선언하고 각 노드들의 관계를 저장
  • 예를 들어, 방향성이 없는 간선으로 1번 정점과 2번 정점이 연결되어 있다면
    Graph[1][2] = Graph[2][1] = 1;
    위와 같이 저장해서 각 정점이 1이라면 이어져 있음을 표시
• 3. 각 노드의 방문 여부를 확인하는 Visited[] 배열을 선언
• 4. DFS를 재귀 함수로 구현하기 위해 따로 메서드로 구현, 매개변수로 시작 Node를 넘김
• 5. DFS 재귀 부분을 작성
  • 방문하지 않았고 ( !Visited[next] )
    간선이 존재 (Graph[node][next] != 0) 한다면 dfs 탐색 진행

    for (int next = 0; next < N; ++next) {
       if(!Visited[next] && Graph[node][next] != 0)
          dfs(next);
    }

 - Java Code

    static final int MAX_N = 1000;
    static int N, E; // N = 노드의 수 , E = 간선의 수
    static int[][] Graph = new int[MAX_N][MAX_N];

    // 방문 여부
    static boolean[] Visited = new boolean[MAX_N];

    // DFS는 재귀함수를 사용한다
    static void dfs(int node) {

        // 방문한 노드를 true로 변경
        Visited[node] = true;

        // 방문한 노드를 출력
        System.out.print(node + " ");

        /*
        다음 노드가 있는지 확인하고 재귀함수 실행
        !Visited[next] : 방문하지 않았고
        !Graph[node][next] != 0 : 간선이 존재한다면
        */
        for (int next = 0; next < N; ++next) {
            if(!Visited[next] && Graph[node][next] != 0)
                dfs(next);
        }
    }

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);

        // 노드 수 입력
        N = scan.nextInt();

        // 간선 수 입력
        E = scan.nextInt();

        for (int i = 0; i < E; i++) {
            int u = scan.nextInt();
            int v = scan.nextInt();

            // u, v 노드 사이에 간선이 존재한다, 간선의 방향을 지정하지 않았기 때문에 역순으로도 1을 해줌.
            Graph[u][v] = Graph[v][u] = 1;
        }

        dfs(0);

    }