Java에서 그래프 탐색 알고리즘 구현하기: DFS와 BFS 소개

그래프 탐색 알고리즘은 데이터 구조의 한 종류인 그래프를 탐색하는 기법입니다. 그래프는 노드(또는 정점)와 이 노드들을 연결하는 엣지(또는 간선)로 구성됩니다. 탐색 알고리즘은 그래프의 모든 노드를 방문하는 과정에서 여러 문제를 해결하는 데 사용됩니다, 예를 들어, 경로 찾기, 네트워크 분석, 소셜 네트워크 서비스의 친구 추천 등에 활용됩니다. Java 프로그래밍 언어는 객체 지향적 특성을 바탕으로 복잡한 그래프 구조를 효과적으로 구현할 수 있습니다. 이 글에서는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 두 가지 기본적인 그래프 탐색 알고리즘을 Java로 구현하는 방법을 소개합니다.

• 깊이 우선 탐색(DFS)

DFS는 그래프의 깊은 부분을 우선적으로 탐색하는 방법입니다. 재귀 함수를 사용하거나 스택을 사용하여 구현할 수 있습니다. DFS는 미로 찾기, 퍼즐 게임 같은 문제를 해결할 때 유용합니다.

 

import java.util.*;

public class Graph {
    private LinkedList<Integer> adjLists[];
    private boolean visited[];

    Graph(int vertices) {
        adjLists = new LinkedList[vertices];
        visited = new boolean[vertices];

        for (int i = 0; i < vertices; i++)
            adjLists[i] = new LinkedList<Integer>();
    }

    void addEdge(int src, int dest) {
        adjLists[src].add(dest);
    }

    void DFS(int vertex) {
        visited[vertex] = true;
        System.out.print(vertex + " ");

        Iterator<Integer> ite = adjLists[vertex].listIterator();
        while (ite.hasNext()) {
            int adj = ite.next();
            if (!visited[adj])
                DFS(adj);
        }
    }

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

        g.DFS(2);
    }
}

 

 

• 너비 우선 탐색(BFS)

BFS는 그래프의 가까운 노드를 우선적으로 탐색하는 방법입니다. 큐를 사용하여 구현하며, BFS는 최단 경로 문제나 소셜 네트워킹 애플리케이션의 친구 추천 기능 구현에 적합합니다.

 

import java.util.*;

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

    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 Breadth First Traversal (starting from vertex 2)");

        g.BFS(2);
    }
}

 

DFS와 BFS는 그래프 탐색의 기본이 되는 알고리즘으로, 다양한 고급 그래프 알고리즘의 기초를 형성합니다. Java에서 이러한 알고리즘을 구현하면, 복잡한 문제를 효과적으로 해결할 수 있으며, 이는 프로그래밍 능력을 크게 향상시키는 데 도움이 됩니다. 실제 어플리케이션 개발에 있어서도, 이러한 탐색 알고리즘은 데이터 분석, 인공 지능, 네트워크 시스템 등 광범위한 분야에서 중요한 역할을 합니다.