- 무방향 그래프: 간선에 방향이 없어 양방향 이동이 가능하다 (예: 도로)
- 방향 그래프: 간선에 방향이 있어 일방통행이다 (예: 팔로우 관계)
- 가중치 그래프: 간선에 비용(거리, 시간 등)이 부여된다
- 구현 방식: 인접 행렬 \(O(V^2)\) vs 인접 리스트 \(O(V+E)\)
- 그래프(graph)란 사물을 정점(vertex)과 간선(edge)으로 나타내기 위한 도구다.
- 그래프는 두 가지 방식으로 구현할 수 있다.
인접 행렬(adjacency matrix): 2차원 배열을 사용하는 방식
인접 리스트(adjacency list): 연결 리스트를 이용하는 방식
- 소셜 네트워크: 사용자(정점)와 팔로우 관계(간선)를 그래프로 표현한다.
- 최단 경로 탐색: 내비게이션의 경로 계산에 그래프 자료구조가 활용된다.
- 추천 시스템: 아이템 간 유사도를 그래프로 모델링한다.
- 인접 행렬은 두 노드의 연결 여부를 \(O(1)\) 에 확인할 수 있어 밀집 그래프에 유리하다.
- 인접 리스트는 \(O(V+E)\) 공간만 사용하여 희소 그래프에 유리하다.
- 인접 행렬(adjacency matrix)에서는 그래프를 2차원 배열로 표현한다.
모든 간선이 방향성을 가지지 않는 그래프를 무방향 그래프라고 한다.
모든 간선에 가중치가 없는 그래프를 무가중치 그래프라고 한다.
무방향 무가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 행렬로 출력할 수 있다.
모든 간선이 방향을 가지는 그래프를 방향 그래프라고 한다.
모든 간선에 가중치가 있는 그래프를 가중치 그래프라고 한다.
방향 가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 행렬로 출력할 수 있다.
- 인접 리스트(adjacency list)에서는 그래프를 리스트로 표현한다.
모든 간선이 방향성을 가지지 않는 그래프를 무방향 그래프라고 한다.
모든 간선에 가중치가 없는 그래프를 무가중치 그래프라고 한다.
무방향 무가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 리스트로 출력할 수 있다.
모든 간선이 방향을 가지는 그래프를 방향 그래프라고 한다.
모든 간선에 가중치가 있는 그래프를 가중치 그래프라고 한다.
방향 가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 리스트로 출력할 수 있다.
- 인접 행렬: 모든 정점들의 연결 여부를 저장해 \(O(V^2)\) 의 공간을 요구한다.
- 공간 효율성이 떨어지지만, 두 노드의 연결 여부를 \(O(1)\) 에 확인할 수 있다.
- 인접 리스트: 연결된 간선의 정보만을 저장하여 \(O(V+E)\) 의 공간을 요구한다.
- 공간 효율성이 우수하지만, 두 노드의 연결 여부를 확인하기 위해 \(O(V)\) 의 시간이 필요하다.
최단 경로 알고리즘을 구현할 때, 어떤 자료구조가 유용할까?
각각 근처의 노드와 연결되어 있는 경우가 많으므로, 간선 개수가 적어 인접 리스트가 유리하다.
- 최단 경로 탐색: 내비게이션(Dijkstra), 소셜 네트워크 친구 추천(BFS)에 그래프가 활용된다.
- 추천 시스템: 사용자-아이템 이분 그래프로 협업 필터링을 구현한다.
- 지식 그래프(Knowledge Graph): 개체(정점)와 관계(간선)를 그래프로 모델링하여 AI 추론에 활용한다.
- 의존성 관리: Python 패키지 의존 관계를 DAG(방향 비순환 그래프)로 표현하여 설치 순서를 결정한다.
- 사기 탐지: 거래 관계를 그래프로 모델링하여 이상 패턴을 탐지한다.
1 그래프(Graph)
그래프는 정점(Vertex, Node)과 간선(Edge)의 집합으로 이루어진 자료구조다.
직관적 이해: 지하철 노선도와 같다. 역(정점)과 노선(간선)으로 구성되며, 두 역이 연결되어 있는지, 최단 환승 경로는 무엇인지를 그래프 알고리즘으로 찾는다.
인접 행렬 vs 인접 리스트 비교:
그래프 (노드 4개): 인접 행렬: 인접 리스트:
0 ─── 1 0 1 2 3 0: [1, 2]
│ │ 0[0,1,1,0] 1: [0, 3]
2 ─── 3 1[1,0,0,1] 2: [0, 3]
2[1,0,0,1] 3: [1, 2]
3[0,1,1,0]
인접 행렬: 0과 3이 연결? → matrix[0][3] == 1 확인, O(1)
인접 리스트: 0과 3이 연결? → 0의 리스트 [1,2] 순회, O(V)2 왜 필요한가
3 인접 행렬(Adjacency Matrix)
3.1 인접 행렬 - 무방향 무가중치 그래프
아래 코드는 4개 노드의 무방향 무가중치 그래프를 인접 행렬로 표현한다. 연결되면 1, 아니면 0을 저장한다.
# 무방향 무가중치 그래프 (노드 4개, 간선: 0-1, 0-2, 1-3, 2-3)
n = 4 # 노드 수
INF = float('inf')
# 인접 행렬 초기화 (연결 없으면 0)
adj_matrix = [[0] * n for _ in range(n)]
# 간선 추가 (무방향: 양쪽에 1 할당)
edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
for u, v in edges:
adj_matrix[u][v] = 1
adj_matrix[v][u] = 1
print("인접 행렬:")
for row in adj_matrix:
print(row)
# 출력:
# 인접 행렬:
# [0, 1, 1, 0]
# [1, 0, 0, 1]
# [1, 0, 0, 1]
# [0, 1, 1, 0]3.2 인접 행렬 - 방향 가중치 그래프
방향 가중치 그래프는 간선 (u, v, w)에서 u→v 방향으로만 이동 가능하고, 비용은 w다. 연결 없는 경우 INF(무한대)로 초기화한다.
# 방향 가중치 그래프 (노드 4개)
n = 4
INF = float('inf')
# 연결 없으면 INF, 자기 자신은 0
adj_matrix = [[INF if i != j else 0 for j in range(n)] for i in range(n)]
# 간선 추가 (방향: u→v, 가중치 w)
edges = [(0, 1, 5), (0, 2, 3), (1, 3, 2), (2, 3, 7)]
for u, v, w in edges:
adj_matrix[u][v] = w
print("방향 가중치 인접 행렬:")
for row in adj_matrix:
print(row)
# 출력:
# 방향 가중치 인접 행렬:
# [0, 5, 3, inf]
# [inf, 0, inf, 2]
# [inf, inf, 0, 7]
# [inf, inf, inf, 0]4 인접 리스트(Adjacency List)
4.1 인접 리스트 - 무방향 무가중치 그래프
인접 리스트는 각 노드의 이웃 노드만 저장하여 메모리를 절약한다. 간선 수가 적은 희소 그래프에 적합하다.
# 무방향 무가중치 그래프 (인접 리스트)
n = 4
adj_list = [[] for _ in range(n)]
edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
for u, v in edges:
adj_list[u].append(v)
adj_list[v].append(u)
print("무방향 무가중치 인접 리스트:")
for i, neighbors in enumerate(adj_list):
print(f" 노드 {i}: {neighbors}")
# 출력:
# 무방향 무가중치 인접 리스트:
# 노드 0: [1, 2]
# 노드 1: [0, 3]
# 노드 2: [0, 3]
# 노드 3: [1, 2]4.2 인접 리스트 - 방향 가중치 그래프
방향 가중치 그래프의 인접 리스트는 (이웃 노드, 가중치) 튜플로 저장한다. Dijkstra 알고리즘의 입력 형식이다.
# 방향 가중치 그래프 (인접 리스트: [(이웃 노드, 가중치)] 형태)
n = 4
adj_list = [[] for _ in range(n)]
edges = [(0, 1, 5), (0, 2, 3), (1, 3, 2), (2, 3, 7)]
for u, v, w in edges:
adj_list[u].append((v, w))
print("방향 가중치 인접 리스트:")
for i, neighbors in enumerate(adj_list):
print(f" 노드 {i}: {neighbors}")
# 출력:
# 방향 가중치 인접 리스트:
# 노드 0: [(1, 5), (2, 3)]
# 노드 1: [(3, 2)]
# 노드 2: [(3, 7)]
# 노드 3: []5 그래프의 시간 복잡도
| Number | Category | 필요한 메모리 | 연결 여부 확인 |
|---|---|---|---|
| 1 | 인접 행렬 | \(O(V^2)\) | \(O(1)\) |
| 2 | 인접 리스트 | \(O(V+E)\) | \(O(V)\) |
See 표 1.
선택 기준: - 노드 수 V가 크고 간선 수 E가 적은 희소 그래프(소셜 네트워크, 도로망)는 인접 리스트가 유리하다. - 노드 수가 적고 두 노드 간 연결 여부를 자주 확인하는 밀집 그래프는 인접 행렬이 유리하다. - 최단 경로(Dijkstra, BFS)는 인접 리스트 + 우선순위 큐 조합이 일반적이다.