Java에서 그래프 알고리즘 구현하기: 기본 개념부터 실용적인 예제까지

그래프 이론은 컴퓨터 과학에서 중요한 위치를 차지하며, 네트워크, 경로 찾기, 최적화 문제 등 다양한 분야에서 응용됩니다. 그래프 알고리즘은 노드(정점)들과 그 노드들을 연결하는 엣지(간선)들로 구성된 그래프 데이터 구조를 사용하여 문제를 해결합니다. Java는 객체 지향 프로그래밍을 통해 복잡한 그래프 알고리즘을 구현하기에 적합한 언어입니다. 본문에서는 그래프의 기본 개념을 소개하고, 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS), 그리고 최단 경로 알고리즘인 다익스트라 알고리즘을 Java로 구현하는 방법을 탐구합니다.

• 그래프의 기본 구조 정의

그래프는 노드와 엣지의 집합으로 정의됩니다. 노드는 그래프에서 개별 항목을, 엣지는 노드 간의 관계를 나타냅니다. 그래프는 방향성이 있는 유향 그래프와 방향성이 없는 무향 그래프로 분류됩니다.

• 깊이 우선 탐색(DFS)

DFS 알고리즘은 그래프의 노드를 깊이 우선으로 탐색하는 방법입니다. 스택이나 재귀를 사용하여 구현할 수 있으며, 노드를 방문하면서 해당 노드와 인접한 노드를 재귀적으로 탐색합니다.

 

void DFSUtil(int v, boolean visited[], List<List<Integer>> adj) {
    // 현재 노드를 방문 처리
    visited[v] = true;
    System.out.print(v + " ");

    // 현재 노드와 인접한 모든 노드를 방문
    for (int x : adj.get(v)) {
        if (!visited[x])
            DFSUtil(x, visited, adj);
    }
}

void DFS(int v, List<List<Integer>> adj) {
    // 노드 방문 여부를 저장할 배열 초기화
    boolean visited[] = new boolean[adj.size()];
    
    // DFS 실행
    DFSUtil(v, visited, adj);
}

 

 

• 너비 우선 탐색(BFS)

BFS 알고리즘은 그래프의 노드를 너비 우선으로 탐색하는 방법입니다. 큐를 사용하여 구현하며, 시작 노드부터 인접한 모든 노드를 방문하고, 이후 이 노드들에 인접한 노드들을 차례대로 방문하는 방식으로 진행됩니다.

 

void BFS(int s, List<List<Integer>> adj) {
    // 노드 방문 여부를 저장할 배열 초기화
    boolean visited[] = new boolean[adj.size()];
    
    // 방문할 노드를 저장할 큐 생성
    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.get(s).listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n]) {
                visited[n] = true;
                queue.add(n);
            }
        }
    }
}

 

 

• 다익스트라 알고리즘

다익스트라 알고리즘은 그래프에서 한 노드로부터 다른 모든 노드까지의 최단 경로를 찾는 알고리즘입니다. 우선순위 큐를 사용하여 더 짧은 경로를 먼저 처리하도록 하여 효율적으로 최단 거리를 계산합니다.

 

이러한 그래프 알고리즘들은 Java를 이용하여 구현할 때 객체 지향적 특성을 활용하여 코드의 가독성과 재사용성을 높일 수 있습니다. 실제로 그래프 기반의 알고리즘 문제를 해결함으로써, Java 프로그래밍 능력과 함께 알고리즘에 대한 이해도를 심화시킬 수 있을 것입니다.