[java] 자바에서 사용하는 그래프 알고리즘

15 Dec 2023

java

자바는 그래프 알고리즘을 구현하는 데 널리 사용되는 언어입니다. 그래프는 정점과 간선으로 이루어진 자료 구조로, 다양한 분야에서 활발하게 활용됩니다. 자바에서 그래프 알고리즘을 사용하는 방법을 알아봅시다.

그래프 표현

그래프는 인접 행렬, 인접 리스트, 혹은 객체 지향적인 방법으로 표현될 수 있습니다.

인접 행렬 (Adjacency Matrix)

인접 행렬은 2차원 배열로 그래프를 표현합니다. graph[i][j] 값이 1일 경우 정점 i와 j 사이에 간선이 있음을 의미합니다.

int[][] graph = new int[V][V]; // V는 정점의 수

인접 리스트 (Adjacency List)

인접 리스트는 리스트나 맵을 사용하여 그래프를 표현합니다.

List<List<Integer>> graph = new ArrayList<>();

객체 지향적 방법

객체 지향적 방법은 정점과 간선을 클래스로 표현하여 그래프를 생성합니다.

public class Graph {
    List<Vertex> vertices;
    List<Edge> edges;
}

그래프 알고리즘

다양한 그래프 알고리즘이 존재합니다. 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)은 가장 기본적인 알고리즘입니다. 또한 최단 경로 탐색을 위한 다익스트라 알고리즘, 벨만-포드 알고리즘, A* 알고리즘 등이 있습니다.

BFS (Breadth-First Search)

void BFS(int start) {
    boolean[] visited = new boolean[V];
    Queue<Integer> queue = new LinkedList<>();
    visited[start] = true;
    queue.add(start);

    while (!queue.isEmpty()) {
        int current = queue.poll();
        System.out.print(current + " ");

        for (int v : graph.get(current)) {
            if (!visited[v]) {
                visited[v] = true;
                queue.add(v);
            }
        }
    }
}

DFS (Depth-First Search)

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

    for (int v : graph.get(current)) {
        if (!visited[v]) {
            DFS(v, visited);
        }
    }
}

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

마치며

자바에서 그래프 알고리즘을 구현하는 방법과 기본 알고리즘들을 알아보았습니다. 그래프는 데이터 구조와 알고리즘에서 중요한 주제이며, 자바를 활용하여 다양한 그래프 기반 애플리케이션 개발이 가능합니다.

자바 그래프 알고리즘에 대해 더 많은 학습을 원하시는 경우, 아래 자료를 참고해보세요.