[3] Graph 의 개념과 인접 행렬, 인접 리스트 판단 기준

Graph 란?

• 그래프(Graph)는 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조

grpah 를 표현하기 위해서는 대표적으로 두가지 방법이 있습니다.

• 인접 리스트

• 인접 행렬

각각의 Vertex와 연결되어있는 Vertex를 표현하기 위한 방법이고, 두 방식의 구현 방법과 상황별로 어떤 상황에서 어떤 구현방식을 선택해야 하는지 알아볼게요!

1. 인접 리스트

해당 코드는 다음과 같아요

import java.util.LinkedList;

public class Graph {
    private int V;  // 정점의 개수
    private LinkedList<Integer>[] adj;  // 인접 리스트

    // 생성자
    @SuppressWarnings("unchecked")
    public Graph(int v) {
        this.V = v;
        adj = new LinkedList[v];
        // 각 정점마다 인접 리스트 초기화
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    // 간선 추가 (무방향 그래프)
    public void addEdge(int v, int w) {
        adj[v].add(w);  // v -> w
        adj[w].add(v);  // w -> v (무방향이므로)
    }

    // v에 인접한 모든 정점 출력
    public void printAdjList(int v) {
        System.out.print("Vertex " + v + " is connected to: ");
        for (int x : adj[v]) {
            System.out.print(x + " ");
        }
        System.out.println();
    }

    // 전체 그래프 출력
    public void printGraph() {
        for (int i = 0; i < V; i++) {
            printAdjList(i);
        }
    }

    // 테스트를 위한 메인 메소드
    public static void main(String[] args) {
        Graph g = new Graph(4);  // 4개의 정점을 가진 그래프

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 3);

        g.printGraph();
    }
}

그렇다면 graph 를 다루는 상황에서 언제 위의 인접 리스트를 선택하게 될까요?

# 희소 그래프(Sparse Graph)
간선의 수가 정점 수의 제곱보다 훨씬 적은 경우 (E << V²)

특징

실제 존재하는 간선만 저장하므로 메모리 효율적
공간 복잡도: O(V + E)

정점 추가/제거
간선 추가/제거
특정 정점의 모든 인접 정점 탐색

2.인접 행렬(Adjacency Matrix)

인접 행렬의 코드는 다음과 같습니다

public class Graph {
    private int V;  // 정점의 개수
    private int[][] adj;  // 인접 행렬

    // 생성자
    public Graph(int v) {
        this.V = v;
        adj = new int[v][v];
        // 행렬 초기화 (모든 값을 0으로)
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < v; j++) {
                adj[i][j] = 0;
            }
        }
    }

    // 간선 추가 (무방향 그래프)
    public void addEdge(int v, int w) {
        adj[v][w] = 1;  // v -> w
        adj[w][v] = 1;  // w -> v (무방향이므로)
    }

    // v에 인접한 모든 정점 출력
    public void printAdjVertex(int v) {
        System.out.print("Vertex " + v + " is connected to: ");
        for (int i = 0; i < V; i++) {
            if (adj[v][i] == 1) {
                System.out.print(i + " ");
            }
        }
        System.out.println();
    }

    // 전체 인접 행렬 출력
    public void printGraph() {
        System.out.println("Adjacency Matrix:");
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                System.out.print(adj[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("\nConnections:");
        for (int i = 0; i < V; i++) {
            printAdjVertex(i);
        }
    }

    // 테스트를 위한 메인 메소드
    public static void main(String[] args) {
        Graph g = new Graph(4);  // 4개의 정점을 가진 그래프

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 3);

        g.printGraph();
    }
}

인접 행렬을 이용하는 경우

밀집 그래프(Dense Graph)
    간선의 수가 정점 수의 제곱에 가까운 경우 (E ≈ V²)

특징

두 정점 간 간선 존재 여부 확인 (O(1))
간선 가중치 수정
간선 추가/제거 (O(1))
그래프 전체 구조를 한눈에 파악해야 하는 경우
가중치가 자주 변경되는 경우
행렬의 값만 변경하면 되므로 효율적

상황별 판단 기준

degree(v)는 정점 v의 차수(연결된 간선의 수)를 의미해요

작업	인접 리스트	인접 행렬
간선 추가	O(1)	O(1)
간선 제거	O(E)	O(1)
간선 존재 확인	O(degree(v))	O(1)
정점의 모든 인접 정점 확인	O(degree(v))	O(V)
그래프의 모든 간선 확인	O(V + E)	O(V²)
메모리	O(V + E)	O(V²)

결론

인접 행렬은 간선 관련 단일 연산(추가/제거/확인)에 강점
인접 리스트는 메모리와 그래프 전체 탐색에 강점