[java] 인접 리스트로 그래프 구현하기

04 Dec 2023

java

그래프는 정점(vertex)과 간선(edge)으로 구성된 자료구조로, 다양한 문제나 알고리즘에서 활용됩니다. 이번 글에서는 그래프를 인접 리스트(adjacency list)로 구현하는 방법에 대해 알아보겠습니다.

인접 리스트란?

인접 리스트는 그래프의 각 정점마다 연결된 정점들을 리스트 형태로 저장하는 방식입니다. 이 방식으로 그래프를 구현하면, 각 정점의 인접한 정점들을 효율적으로 탐색할 수 있습니다.

그래프 구현하기

다음은 Java 언어를 사용하여 인접 리스트로 그래프를 구현하는 간단한 예제 코드입니다. 아래 코드를 참고하여 그래프를 만들고, 정점과 간선을 추가하고, 인접한 정점들을 탐색해보세요.

import java.util.*;

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

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

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

    public void printAdjacentVertices(int vertex) {
        System.out.println("Adjacent vertices of " + vertex + ":");
        for (int v : adjList[vertex]) {
            System.out.print(v + " ");
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(5);

        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);
        
        graph.printAdjacentVertices(0);
        graph.printAdjacentVertices(1);
        graph.printAdjacentVertices(2);
        graph.printAdjacentVertices(3);
        graph.printAdjacentVertices(4);
    }
}

위 코드에서 Graph 클래스는 그래프를 나타내며, addEdge 메소드는 간선을 추가하는 역할을 수행합니다. printAdjacentVertices 메소드는 주어진 정점의 인접한 정점들을 출력합니다.

실행 결과

위의 예제 코드를 실행하면 다음과 같은 출력 결과를 얻을 수 있습니다.

Adjacent vertices of 0:
1 4 
Adjacent vertices of 1:
0 2 3 4 
Adjacent vertices of 2:
1 3 
Adjacent vertices of 3:
1 2 4 
Adjacent vertices of 4:
0 1 3 

인접 리스트란?

그래프 구현하기

실행 결과

참고 자료