[java] 자바의 깊이 우선 탐색(Depth First Search, DFS) 알고리즘 이해하기

14 Dec 2023

java

깊이 우선 탐색(Depth First Search, DFS) 알고리즘

깊이 우선 탐색은 그래프를 탐색하는 방법 중 하나로, 한 정점에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 알고리즘입니다. 이 알고리즘은 스택(Stack) 또는 재귀 함수를 사용하여 구현할 수 있습니다.

자바를 사용한 DFS 알고리즘 구현

다음은 자바를 사용하여 깊이 우선 탐색 알고리즘을 구현한 예제입니다.

import java.util.*;

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);
    }

    void DFSUtil(int v, boolean visited[]) {
        visited[v] = true;

        System.out.print(v + " ");

        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n]) {
                DFSUtil(n, visited);
            }
        }
    }

    void DFS(int v) {
        boolean visited[] = new boolean[V];
        DFSUtil(v, visited);
    }

    public static void main(String args[]) {
        Graph g = new Graph(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("Following is Depth First Traversal " + "(starting from vertex 2)");

        g.DFS(2);
    }
}

결론

이제 당신은 깊이 우선 탐색(Depth First Search, DFS) 알고리즘에 대해 알게 되었고, 자바를 사용하여 이를 구현하는 방법을 배웠습니다. 이해하기 쉽고 유용한 DFS 알고리즘은 다양한 분야에서 활용될 수 있으며, 그래프 탐색과 관련된 여러 문제를 해결하는 데 도움이 될 것입니다.

이 포스트를 통해 DFS 알고리즘에 대한 이해를 높이고, 자바를 활용하여 실제로 구현해볼 수 있었기를 바랍니다.

참고 문헌: GeeksforGeeks - Depth First Search or DFS for a Graph