[java] 자바로 그래프 탐색 알고리즘 구현하기

15 Dec 2023

java

이번 포스트에서는 그래프 구조를 사용하여 탐색 알고리즘을 구현하는 방법에 대해 알아보겠습니다.

그래프란 무엇인가요?

그래프는 정점(vertex)과 간선(edge)의 집합으로 구성된 자료 구조입니다. 이는 실제 세계의 네트워크를 모델링하는 데 적합한 구조로 사용됩니다. 그래프는 방향 그래프와 무방향 그래프, 가중치 그래프 등 다양한 형태가 있습니다.

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

깊이 우선 탐색(DFS)은 그래프를 탐색하는 한 가지 방법으로, 더 이상 탐색할 곳이 없을 때까지 갈 수 있는 만큼 깊게 탐색하는 방법입니다.

import java.util.*;

class DFS {
    private int V; // 그래프의 정점 개수
    private LinkedList<Integer> adj[]; // 인접 리스트

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

너비 우선 탐색(BFS) 알고리즘

너비 우선 탐색(BFS)은 그래프를 탐색하는 또 다른 방법으로, 시작 정점으로부터 거리에 따라 단계별로 탐색하는 방법입니다.

import java.util.*;

class BFS {
    private int V; // 그래프의 정점 개수
    private LinkedList<Integer> adj[]; // 인접 리스트

    BFS(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 bfs(int s) {
        boolean visited[] = new boolean[V];

        LinkedList<Integer> queue = new LinkedList<Integer>();

        visited[s] = true;
        queue.add(s);

        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s + " ");

            Iterator<Integer> i = adj[s].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

그래프 알고리즘을 자바로 구현하는 방법에 대해 간단히 살펴보았습니다. 다양한 그래프 탐색 알고리즘을 구현하고, 실제 응용 프로그램에서 활용해 보시기 바랍니다.

참고 자료

GeeksforGeeks: Graph Data Structure