인접 행렬 vs 인접 리스트

백엔드&인프라 추종자·2025년 4월 2일

코딩테스트 공부

목록 보기

6/10

개인생각

인접 리스트 하나만 익혀둘거다.. 어려움.. (머리가 나쁘다 ㅋㅋㅋ)

인접 행렬 vs. 인접 리스트: 어떤 방식이 더 좋을까?

그래프를 표현하는 방법에는 크게 인접 행렬(Adjacency Matrix) 과 인접 리스트(Adjacency List) 두 가지가 있습니다.
어떤 방식이 더 좋은지는 그래프의 특징(노드 수, 간선 수) 에 따라 다릅니다.

1. 인접 행렬 (Adjacency Matrix)

✅ 구조:

N x N 크기의 2차원 배열을 사용해 모든 노드 간의 연결 정보를 저장
graph[i][j] = 1 (i에서 j로 가는 간선이 존재)
graph[i][j] = 0 (i에서 j로 가는 간선이 없음)

✅ 코드 예제 (인접 행렬)

# 노드가 4개인 그래프
graph = [
    [0, 1, 1, 0],  # 0번 노드 → 1, 2번 노드와 연결
    [1, 0, 0, 1],  # 1번 노드 → 0, 3번 노드와 연결
    [1, 0, 0, 1],  # 2번 노드 → 0, 3번 노드와 연결
    [0, 1, 1, 0]   # 3번 노드 → 1, 2번 노드와 연결
]

🔹 장점 (장점이 많은 상황)

장점	설명
간선 존재 여부 확인이 빠름	`O(1)`로 `graph[i][j]`만 확인하면 연결 여부를 즉시 알 수 있음
구현이 간단함	2차원 배열만 사용하므로 구현이 직관적
고정된 크기의 메모리 사용	`N x N` 배열을 사용하므로, 노드 수가 적다면 효과적

🔹 단점 (비효율적인 상황)

단점	설명
메모리 사용량이 많음	간선이 적은 희소 그래프(Sparse Graph, 간선이 적은 그래프) 에서도 `N^2` 공간을 차지함
연결된 노드 찾기 느림	`O(N)` 시간이 걸림 (모든 행을 탐색해야 함)

2. 인접 리스트 (Adjacency List)

✅ 구조:

각 노드에 대해 연결된 노드만 리스트로 저장
graph[i] = [연결된 노드 목록]

✅ 코드 예제 (인접 리스트)

graph = {
    0: [1, 2],    # 0번 노드는 1, 2번과 연결
    1: [0, 3],    # 1번 노드는 0, 3번과 연결
    2: [0, 3],    # 2번 노드는 0, 3번과 연결
    3: [1, 2]     # 3번 노드는 1, 2번과 연결
}

🔹 장점 (장점이 많은 상황)

장점	설명
메모리 사용량이 적음	`O(N + M)`만 사용 → 희소 그래프(Sparse Graph) 에서 유리
연결된 노드 탐색이 빠름	연결된 노드만 저장하므로 `O(노드의 차수)` 만에 탐색 가능

🔹 단점 (비효율적인 상황)

단점	설명
간선 존재 여부 확인이 느림	특정 노드 간의 연결 여부를 확인하려면 리스트를 탐색해야 해서 `O(N)` 이 걸릴 수 있음
연결이 적은 그래프에서 추가적인 포인터 사용	리스트 구조라 포인터(링크) 사용으로 추가 메모리 소모

3. 인접 행렬 vs. 인접 리스트 비교 정리

비교 항목	인접 행렬	인접 리스트
메모리 사용량	`O(N^2)` (모든 노드의 간선 저장)	`O(N + M)` (연결된 간선만 저장)
간선 존재 확인	`O(1)` (배열 조회)	`O(N)` (리스트 탐색)
연결된 노드 찾기	`O(N)` (전체 탐색)	`O(노드의 차수)` (리스트 순회)
그래프 크기	노드 수가 적고 밀도가 높은 그래프에 적합	희소 그래프(간선이 적은 그래프)에 적합
구현 난이도	쉬움 (2차원 배열)	다소 복잡 (리스트)

4. 어떤 경우에 어떤 방식을 선택할까?

상황	더 적합한 방식
노드 수가 많고, 간선이 적음 (희소 그래프)	인접 리스트 (`O(N + M)`)
노드 수가 적고, 간선이 많음 (밀집 그래프)	인접 행렬 (`O(N^2)`)
간선 존재 여부를 빠르게 확인해야 함	인접 행렬 (`O(1)`)
연결된 노드를 빠르게 탐색해야 함	인접 리스트 (`O(노드 차수)`)