그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조로, 다양한 알고리즘에서 활용됩니다. 그래프를 저장하는 방식에 따라 성능과 메모리 사용량이 달라질 수 있기 때문에, 그래프를 표현하는 방법을 잘 이해하는 것이 중요합니다. 이번 블로그에서는 그래프를 표현하는 세 가지 방법을 소개하고, 각 방식의 장단점을 비교해 보겠습니다.

1. 그래프 표현 방식

1.1 엣지 리스트 (Edge List)

엣지 리스트는 그래프의 간선을 리스트로 저장하는 방식입니다. 각 간선은 (정점1, 정점2) 또는 (정점1, 정점2, 가중치) 형태로 저장됩니다.

특징

• 메모리를 적게 사용하지만, 특정 정점과 연결된 간선을 찾는 데 시간이 오래 걸립니다.
• 간선이 많아질수록 탐색 속도가 느려집니다.

예제 (무방향 그래프)

# (정점1, 정점2, 가중치) 형태로 저장
edges = [
    (1, 2, 4),
    (1, 3, 2),
    (2, 3, 5),
    (2, 4, 10),
    (3, 4, 3)
]

1.2 인접 행렬 (Adjacency Matrix)

인접 행렬은 그래프를 2차원 배열로 표현하는 방식입니다. 행과 열은 정점을 나타내며, 두 정점이 연결되어 있으면 해당 위치에 1(또는 가중치)을 저장하고, 연결되지 않았으면 0을 저장합니다.

특징

• 특정 두 정점이 연결되어 있는지 빠르게 확인할 수 있습니다. (O(1))
• 그러나 메모리를 많이 사용하므로, 간선이 적은 희소 그래프(Sparse Graph)에서는 비효율적입니다.

예제 (무방향 그래프)

# 4개의 정점을 가진 그래프
n = 4
adj_matrix = [[0] * (n + 1) for _ in range(n + 1)]

# 간선 추가
edges = [
    (1, 2, 4),
    (1, 3, 2),
    (2, 3, 5),
    (2, 4, 10),
    (3, 4, 3)
]

for u, v, w in edges:
    adj_matrix[u][v] = w
    adj_matrix[v][u] = w  # 무방향 그래프

# 출력
for row in adj_matrix:
    print(row)

1.3 인접 리스트 (Adjacency List)

인접 리스트는 각 정점마다 연결된 정점들을 리스트 형태로 저장하는 방식입니다.

특징

• 메모리 사용량이 적고, 특정 정점과 연결된 노드를 쉽게 찾을 수 있어 가장 많이 사용되는 방식입니다.
• 하지만 특정 두 정점이 연결되어 있는지 확인하려면 리스트를 탐색해야 합니다. (O(V), V는 연결된 정점 개수)

예제 (무방향 그래프)

from collections import defaultdict

adj_list = defaultdict(list)

# 간선 추가
edges = [
    (1, 2, 4),
    (1, 3, 2),
    (2, 3, 5),
    (2, 4, 10),
    (3, 4, 3)
]

for u, v, w in edges:
    adj_list[u].append((v, w))
    adj_list[v].append((u, w))  # 무방향 그래프

# 출력
for key in adj_list:
    print(f"{key}: {adj_list[key]}")

2. 그래프 표현 방식 비교

• 엣지 리스트: 그래프를 단순한 데이터 구조로 저장할 때 유용함.
• 인접 행렬: 정점 간 연결 여부를 빠르게 확인해야 할 때 적합함.
• 인접 리스트: 메모리 효율적이며, 연결된 정점을 빠르게 찾을 수 있어 BFS, DFS 같은 그래프 탐색에서 많이 사용됨.

3. 결론

그래프를 표현하는 방법은 문제의 성격에 따라 다르게 선택해야 합니다.

• 간선이 적고 정점이 많은 희소 그래프(Sparse Graph)에서는 인접 리스트가 효과적입니다.
• 정점 개수가 작고 간선이 많은 밀집 그래프(Dense Graph)에서는 인접 행렬이 유리합니다.
• 정점 간 연결 여부보다는 간선 자체에 대한 정보가 중요한 경우에는 엣지 리스트가 적합합니다.