[java] 자바에서 사용하는 DFS 알고리즘

15 Dec 2023

java

DFS(깊이 우선 탐색)는 그래프 구조를 탐색하기 위한 알고리즘 중 하나입니다. 이 알고리즘은 그래프의 모든 정점을 방문하고자 할 때 활용됩니다. 이번 글에서는 자바에서 DFS 알고리즘을 구현하는 방법에 대해 알아보겠습니다.

DFS 알고리즘 개요

DFS 알고리즘은 그래프를 탐색하면서 한 정점으로부터 다른 정점으로 이동해가는 방식입니다. 이 과정에서 아직 방문하지 않은 정점을 만나면 해당 정점으로 이동하여 탐색을 계속 진행합니다. DFS 알고리즘은 재귀적으로 구현될 수 있으며, 스택 자료구조를 사용하여 반복적으로 구현할 수도 있습니다.

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

다음은 자바를 사용하여 DFS 알고리즘을 구현한 간단한 예제 코드입니다.

import java.util.List;
import java.util.Stack;

public class Graph {
    private int V;
    private List<Integer>[] adj;

    public Graph(int V) {
        this.V = V;
        adj = new List[V];
        for (int i = 0; i < V; ++i)
            adj[i] = new ArrayList();
    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
    }

    public void DFS(int s) {
        boolean[] visited = new boolean[V];
        Stack<Integer> stack = new Stack<>();
        stack.push(s);

        while (!stack.empty()) {
            s = stack.pop();

            if (!visited[s]) {
                System.out.print(s + " ");
                visited[s] = true;
            }

            for (int n : adj[s]) {
                if (!visited[n]) {
                    stack.push(n);
                }
            }
        }
    }
}

위 코드는 그래프를 인접 리스트로 표현하고, 해당 그래프에 DFS 알고리즘을 적용하는 예제입니다.

DFS 알고리즘은 그래프 탐색 문제를 해결하는 데에 유용하게 활용될 수 있습니다. 추가로 해당 알고리즘의 시간 복잡도 및 공간 복잡도를 고려하여 실제 상황에 맞게 적용하는 것이 중요합니다.