깊이 우선 탐색(DFS)

깊이 우선 탐색(DFS)

DFS(Depth First Search)는 그래프(Graph)나 트리(Tree)에서 사용되는 탐색 알고리즘입니다.

 

DFS의 동작 원리

1. 시작 노드를 방문합니다. (시작 노드 방문)
2. 방문하지 않은 노드가 있으면 해당 노드로 이동합니다. (인접 노드 탐색)
3. 더 이상 방문할 노드가 없을 때까지 탐색을 반복합니다. (반복)
4. 더 이상 방문할 노드가 없으면 이전 노드로 돌아갑니다. (백트래킹)
5. 모든 노드를 탐색할 때까지 반복합니다 (모든 노드 탐색)

 

DFS 구현 방법

 

위와 같이 노드가 있다 가정하겠습니다.

 

import java.util.*;

public class DFS {
    // 그래프를 인접 리스트로 표현
    static 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);
        }

        // DFS 메서드
        void DFSUtil(int v, boolean[] visited) {
            // 현재 노드 방문
            visited[v] = true;
            System.out.print(v + " ");

            // 모든 인접 노드 탐색
            for (int neighbor : adj[v]) {
                if (!visited[neighbor]) {
                    DFSUtil(neighbor, visited); // 재귀 호출
                }
            }
        }

        // DFS 시작점
        void DFS(int startNode) {
            boolean[] visited = new boolean[V]; // 방문 여부 확인 배열
            DFSUtil(startNode, visited);
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(6); // 노드가 5개 (0번 노드는 사용하지 않음)

        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 5);

        System.out.println("DFS 탐색 결과:");
        graph.DFS(1); // 1번 노드부터 시작
    }
}

 

실행 결과