[java] 자바의 그래프(Graph) 자료구조 이해하기

14 Dec 2023

java

그래프(Graph)는 여러 개의 정점(Vertex)과 이를 연결하는 간선(Edge)으로 이루어진 자료구조입니다. 자바에서 그래프를 표현하고 다루는 방법에 대해 알아보겠습니다.

그래프의 표현

그래프는 인접 행렬(Adjacency Matrix)이나 인접 리스트(Adjacency List)를 사용하여 표현할 수 있습니다. 인접 행렬은 2차원 배열을 사용해 각 정점 사이의 연결 여부를 나타내며, 인접 리스트는 각 정점마다 인접한 정점들을 연결 리스트로 표현합니다.

인접 행렬을 사용한 그래프 구현

class Graph {
    private int V;
    private int[][] adjMatrix;

    public Graph(int v) {
        V = v;
        adjMatrix = new int[V][V];
    }

    public void addEdge(int source, int destination) {
        adjMatrix[source][destination] = 1;
        adjMatrix[destination][source] = 1;
    }
}

인접 리스트를 사용한 그래프 구현

import java.util.LinkedList;

class Graph {
    private int V;
    private LinkedList<Integer>[] adjList;

    public Graph(int v) {
        V = v;
        adjList = new LinkedList[V];
        for (int i = 0; i < V; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int source, int destination) {
        adjList[source].add(destination);
        adjList[destination].add(source);
    }
}

그래프 알고리즘

그래프 자료구조를 사용하여 다양한 알고리즘을 구현할 수 있습니다. 대표적인 그래프 알고리즘으로는 깊이 우선 탐색(DFS)이나 너비 우선 탐색(BFS) 등이 있습니다.

마치며

이러한 방법을 통해 자바에서 그래프를 표현하고 다루는 방법에 대해 알아보았습니다. 그래프는 실생활에서도 자주 활용되며, 알고리즘 문제 해결에도 중요한 자료구조 중 하나입니다.

참고 문헌: GeeksforGeeks