[java] 깊이 우선 탐색 알고리즘 (DFS)

04 Dec 2023

java

깊이 우선 탐색 알고리즘(Depth-First Search, DFS)은 그래프 탐색 알고리즘 중 하나로, 노드를 끝까지 탐색한 후 다른 경로로 백트래킹하여 탐색을 계속하는 방식입니다. 이 알고리즘은 스택(Stack) 자료구조를 사용하여 구현할 수 있습니다.

알고리즘 동작 원리

시작 노드를 스택에 push합니다.
스택에서 노드를 pop하고, 해당 노드가 방문되지 않았다면 방문 표시를 합니다.
현재 노드와 인접한 모든 노드 중 방문되지 않은 노드가 있다면, 해당 노드를 스택에 push합니다.
스택이 빌 때까지 2단계부터 3단계를 반복합니다.

구현 예제

다음은 DFS 알고리즘을 Java로 구현한 코드입니다.

import java.util.ArrayList;
import java.util.Stack;

class Graph {
    private int vertices;
    private ArrayList<ArrayList<Integer>> adjacencyList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjacencyList = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            adjacencyList.add(new ArrayList<>());
        }
    }

    public void addEdge(int source, int destination) {
        adjacencyList.get(source).add(destination);
    }

    public void depthFirstSearch(int start) {
        boolean[] visited = new boolean[vertices];
        Stack<Integer> stack = new Stack<>();
        visited[start] = true;
        stack.push(start);
        
        while (!stack.isEmpty()) {
            int current = stack.pop();
            System.out.print(current + " ");

            for (int neighbor : adjacencyList.get(current)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    stack.push(neighbor);
                }
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(7);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 5);
        graph.addEdge(2, 6);

        System.out.println("깊이 우선 탐색 결과:");
        graph.depthFirstSearch(0);
    }
}

위의 예제는 7개의 정점을 가진 그래프에서 깊이 우선 탐색을 수행하는 코드입니다. 시작 정점은 0으로 설정하였으며, 그래프에서 각 정점 간의 연결 관계는 addEdge 메소드를 통해 설정할 수 있습니다.

참고 자료

Depth-First Search (DFS) Algorithm