BioPlayground

🧬
목록으로

그래프 — 인접행렬 vs 인접리스트

그래프를 코드로 표현하는 두 가지 방법(인접행렬, 인접리스트)의 구조, 장단점, 선택 기준을 설명합니다.

중급
|
5분
|
검증 완료 (2026-07)
진행률0/22 (0%)

그래프 — 인접행렬 vs 인접리스트

이 토픽을 마치면

그래프가 무엇인지, 그리고 인접행렬과 인접리스트 두 가지 표현 방식의 차이를 이해하게 됩니다.

트리는 그래프의 특수한 경우입니다

배열, 연결 리스트, 트리 — 지금까지 본 자료구조들은 데이터 사이의 관계가 단순합니다. 배열은 순서, 트리는 계층입니다.

하지만 현실의 관계는 복잡합니다. SNS에서 사람들은 서로 팔로우합니다. 도시들은 도로로 연결됩니다. 웹페이지들은 링크로 이어집니다. 이런 다대다 관계를 표현하는 자료구조가 **그래프(Graph)**입니다.

그래프는 **노드(Node, 또는 정점 Vertex)**와 노드를 잇는 **간선(Edge)**으로 구성됩니다. 트리도 그래프의 일종이지만, "부모-자식" 제약과 "사이클 없음" 조건이 있는 특수한 그래프입니다.

방향 그래프 vs 무방향 그래프

무방향 그래프: A와 B가 연결되면 A→B, B→A 양쪽 다 갈 수 있습니다. 페이스북 친구 관계처럼 — 내가 친구면 상대도 친구입니다.

방향 그래프(Directed Graph): A→B만 가능하고 B→A는 안 될 수 있습니다. 인스타그램 팔로우처럼 — 내가 팔로우한다고 상대가 나를 팔로우하지는 않습니다.

인접행렬: 2차원 배열

노드가 5개인 그래프를 5×5 행렬로 표현합니다. matrix[i][j] = 1이면 노드 i에서 j로 간선이 있다는 뜻입니다.

text
A  B  C  D
A [ 0, 1, 1, 0 ]
B [ 1, 0, 0, 1 ]
C [ 1, 0, 0, 1 ]
D [ 0, 1, 1, 0 ]

A-B, A-C, B-D, C-D가 연결된 무방향 그래프입니다. 무방향이라 행렬이 대각선 기준으로 대칭입니다.

python
graph = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0],
]


# A와 B가 연결됐는지 확인
if graph[0][1] == 1:
    print("A-B 연결됨")  # O(1)

장점: 두 노드가 연결됐는지 확인하는 게 **O(1)**입니다. 인덱스로 바로 접근합니다.

단점: 노드가 N개면 N×N 크기의 배열이 필요합니다. 노드가 10,000개면 1억 개의 칸이 필요합니다. 간선이 별로 없어도 공간을 다 차지합니다.

인접리스트: 연결 목록

각 노드마다 "이 노드와 연결된 노드 목록"을 저장합니다.

text
A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]

같은 그래프인데 표현 방식이 다릅니다.

python
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C'],
}


# A의 이웃 노드 순회
for neighbor in graph['A']:
    print(neighbor)  # B, C

장점: 간선 수에 비례하는 메모리만 씁니다. 노드가 10,000개여도 간선이 100개면 100개분의 공간만 필요합니다.

단점: 두 노드가 연결됐는지 확인하려면 리스트를 순회해야 합니다. 최악의 경우 **O(N)**입니다.

어떤 걸 써야 하나

text
| 인접행렬          | 인접리스트
---------+------------------+------------------
공간      | O(V^2)           | O(V + E)
연결 확인  | O(1)             | O(degree)
이웃 순회  | O(V)             | O(degree)
적합한 경우 | 간선이 많은 밀집 그래프 | 간선이 적은 희소 그래프

밀집 그래프(Dense Graph): 노드 대비 간선이 많습니다. 모든 도시 간 직항 노선이 있는 항공망. 인접행렬이 적합합니다.

희소 그래프(Sparse Graph): 노드 대비 간선이 적습니다. SNS에서 1억 명 중 각 사용자가 평균 200명만 팔로우. 인접리스트가 적합합니다.

대부분의 실무 그래프는 희소 그래프입니다. 그래서 인접리스트가 기본 선택입니다. 코딩 테스트에서도 인접리스트를 먼저 떠올리면 됩니다.

가중치 그래프

간선에 **가중치(Weight)**가 붙을 수 있습니다. 도시 간 거리, 네트워크 지연 시간 같은 것입니다.

인접행렬에서는 1 대신 가중치 값을 넣습니다:

python
# matrix[A][B] = 거리
matrix = [
    [0, 5, 3, 0],
    [5, 0, 0, 2],
    ...
]

인접리스트에서는 튜플로 표현합니다:

python
graph = {
    'A': [('B', 5), ('C', 3)],
    'B': [('A', 5), ('D', 2)],
    ...
}

가중치 그래프에서 최단 경로를 찾으려면 BFS 대신 다익스트라(Dijkstra) 알고리즘을 씁니다. BFS는 간선 수 기준 최단, 다익스트라는 가중치 합 기준 최단입니다.

핵심

그래프는 노드와 간선으로 다대다 관계를 표현하는 자료구조입니다. 인접행렬은 연결 확인이 O(1)이지만 공간을 O(V^2) 씁니다. 인접리스트는 공간을 O(V+E)만 쓰고, 대부분의 실무 그래프에서 기본 선택입니다.