인접리스트 Tip (list)

그래프의 실전 구현 - 인접 리스트 (Adjacency List)

그래프를 컴퓨터 메모리 상에 표현하는 방법 중 가장 자주 사용되는 방식이 인접 리스트(Adjacency List) 이다.

이 방식은 메모리 효율이 높고, 연결된 노드들만 저장하기 때문에 희소 그래프(Sparse Graph) 에 특히 유리하다.

1. 인접 리스트란?

인접 리스트는 각 정점마다 연결된 정점들의 목록을 따로 저장하는 구조입니다. 자바에서는 이를 List<List<Integer>> 형태로 구현한다.

아래는 8개의 정점을 갖는 무방향 그래프를 인접 리스트로 표현한 코드입니다:

List<List<Integer>> graph = new ArrayList<>() {{
    add(List.of(1, 3, 6));     // 정점 0
    add(List.of(0, 3));        // 정점 1
    add(List.of(3));           // 정점 2
    add(List.of(0, 1, 2, 7));  // 정점 3
    add(List.of(5));           // 정점 4
    add(List.of(4, 6, 7));     // 정점 5
    add(List.of(0, 5));        // 정점 6
    add(List.of(3, 5));        // 정점 7
}};

 

2. 간선 정보로부터 인접 리스트 구성하기

실전 문제에서는 보통 간선 리스트(edge list) 형식으로 입력이 주어지며, 이를 직접 인접 리스트로 변환해야 한다.

예시 입력

int[][] edges = {
    {0, 1}, {0, 3}, {0, 6},
    {1, 3}, {2, 3}, {3, 7},
    {4, 5}, {5, 6}, {5, 7}
};
int n = 8; // 정점 개수

무방향 그래프 변환 코드

List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
    graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
    int a = edge[0], b = edge[1];
    graph.get(a).add(b);
    graph.get(b).add(a); // 무방향일 경우
}

방향 그래프 변환 코드

List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
    graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
    int from = edge[0], to = edge[1];
    graph.get(from).add(to); // 단방향일 경우
}

 

 

4. 연결된 노드 순회하기

기본 반복문

int curVertex = 3;  // 현재 노드

for (int nextVertex : graph.get(curVertex)) {
    System.out.println("현재: " + curVertex + " → 연결: " + nextVertex);
}

출력 예시

현재: 3 → 연결: 0
현재: 3 → 연결: 1
현재: 3 → 연결: 2
현재: 3 → 연결: 7