그래프는 **정점(vertex)**과 **간선(edge)**으로 구성된 자료구조로, 다양한 관계를 표현하는 데 사용된다. 이 자료구조는 완전 탐색 알고리즘인 DFS, BFS, 백트래킹의 기반이 된다.
1. 📊 그래프 기본 개념과 종류
1.1. 구성 요소
– 정점(Vertex/Node): 그래프의 각 지점을 나타내며, 보통 V로 표기한다.
– 간선(Edge): 정점들을 연결하는 선으로, 보통 E로 표기한다.
– 그래프는 G = (V, E)로 표현할 수 있다.
1.2. 방향성에 따른 분류
– 무방향 그래프: 간선에 방향이 없어 양쪽으로 이동 가능하였다.
– 방향 그래프: 간선에 방향이 있어 한쪽으로만 이동 가능하였다.
– 양방향 그래프: 무방향 그래프와 동일한 개념이다.
1.3. 순환성에 따른 분류
– 순환 그래프(Cyclic): 사이클이 하나 이상 존재하는 그래프이다.
– 비순환 그래프(Acyclic): 사이클이 없는 그래프이다.
– DAG(Directed Acyclic Graph): 방향성이 있으면서 사이클이 없는 그래프이다.
- 버전 관리 시스템의 커밋 기록이 대표적인 예시이다.
1.4. 연결성에 따른 분류
– 연결 요소(Connected Component): 서로 연결된 정점들의 집합이다.
– 하나의 그래프에 여러 연결 요소가 존재할 수 있다.
– 정점만 있고 간선이 없는 그래프는 정점 수만큼 연결 요소가 존재한다.
2. 🌲 트리의 특성과 구조
2.1. 트리의 정의
– 트리: 사이클이 없는 무방향 그래프이다.
– 노드 개수 = 간선 개수 + 1 공식이 항상 성립한다.
– 모든 노드 쌍 사이에 경로가 유일하게 존재한다.
2.2. 트리의 구성 요소
– 루트 노드: 트리의 최상위 노드로, 부모가 없는 노드이다.
– 리프 노드: 자식이 없는 노드로, 트리의 가장 바깥쪽에 위치한다.
– 부모-자식 관계: 방향성 트리에서 상위 노드와 하위 노드 간의 관계이다.
2.3. 노드의 위치 관련 개념
– 깊이(Depth): 루트 노드에서 해당 노드까지의 간선 개수이다.
– 높이(Height): 해당 노드에서 리프 노드까지의 간선 개수이다.
– 레벨(Level): 루트 노드에서 해당 노드까지의 간선 개수 + 1이다.
3. 💻 파이썬 코드 구현 방법
3.1. 인접 행렬(Adjacency Matrix)
– 2차원 배열로 그래프를 표현하는 방법이다.
– 공간 복잡도는 **O(V²)**로, 정점 수의 제곱만큼 메모리를 사용한다.
– 간선 존재 여부 확인이 O(1) 시간에 가능하였다.
– 모든 간선 정보를 저장하므로 간선이 많은 경우 적합하다.
// 무방향 그래프의 인접 행렬 예시 (0~3번 노드)
[
[0, 1, 1, 1], // 0번 노드는 1,2,3번과 연결
[1, 0, 1, 0], // 1번 노드는 0,2번과 연결
[1, 1, 0, 1], // 2번 노드는 0,1,3번과 연결
[1, 0, 1, 0] // 3번 노드는 0,2번과 연결
]3.2. 인접 리스트(Adjacency List)
– 각 정점에 연결된 정점들의 리스트로 표현하는 방법이다.
– 공간 복잡도는 **O(E)**로, 간선 수에 비례하는 메모리를 사용한다.
– 간선 존재 여부 확인이 O(V) 시간이 소요되었다.
– 간선이 적은(희소) 그래프에 메모리 효율이 좋다.
// 무방향 그래프의 인접 리스트 예시 (0~3번 노드)
[
[1, 2, 3], // 0번 노드는 1,2,3번과 연결
[0, 2], // 1번 노드는 0,2번과 연결
[0, 1, 3], // 2번 노드는 0,1,3번과 연결
[0, 2] // 3번 노드는 0,2번과 연결
]3.3. 구현 방법 비교
– 인접 행렬: 공간을 많이 사용하지만, 시간 효율성이 좋다.
– 인접 리스트: 공간 효율성이 좋지만, 시간이 더 소요된다.
– 간선 수가 적은 그래프는 인접 리스트가 유리하다.
– 간선 수가 많은 그래프는 인접 행렬이 유리하다.
🖥️ 그래프 구현: 파이썬 코드 예시
1. 인접 행렬(Adjacency Matrix) 구현
1.1. 무방향 그래프
def create_adj_matrix(vertices, edges):
matrix = [[0] * vertices for _ in range(vertices)]
for u, v in edges:
matrix[u][v] = 1
matrix[v][u] = 1 # 무방향 그래프이므로 양방향 설정
return matrix
# 예시: 4개 노드 (0~3)의 무방향 그래프
vertices = 4
edges = [(0,1), (0,2), (0,3), (1,2), (2,3)]
adj_matrix = create_adj_matrix(vertices, edges)
# 출력 결과:
# [
# [0, 1, 1, 1],
# [1, 0, 1, 0],
# [1, 1, 0, 1],
# [1, 0, 1, 0]
# ]1.2. 방향 그래프
def create_directed_adj_matrix(vertices, edges):
matrix = [[0] * vertices for _ in range(vertices)]
for u, v in edges:
matrix[u][v] = 1 # 단방향만 설정
return matrix2. 인접 리스트(Adjacency List) 구현
2.1. 무방향 그래프
def create_adj_list(vertices, edges):
graph = {i: [] for i in range(vertices)}
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # 무방향 그래프이므로 양방향 추가
return graph
# 예시: 4개 노드 (0~3)의 무방향 그래프
edges = [(0,1), (0,2), (0,3), (1,2), (2,3)]
adj_list = create_adj_list(4, edges)
# 출력 결과:
# {
# 0: [1, 2, 3],
# 1: [0, 2],
# 2: [0, 1, 3],
# 3: [0, 2]
# }2.2. 방향 그래프
def create_directed_adj_list(vertices, edges):
graph = {i: [] for i in range(vertices)}
for u, v in edges:
graph[u].append(v) # 단방향만 추가
return graph3. 구현 방법 비교 표
| 특성 | 인접 행렬 | 인접 리스트 |
|---|---|---|
| 공간 복잡도 | O(V²) | O(V + E) |
| 간선 확인 속도 | O(1) | O(V) |
| 간선 추가 속도 | O(1) | O(1) |
| 이웃 탐색 속도 | O(V) | O(1) (해당 노드의 이웃 수만큼) |
| 최적 사용 경우 | 밀집 그래프 (E ≈ V²) | 희소 그래프 (E ≪ V²) |
| 메모리 효율성 | 낮음 (모든 가능한 간선 저장) | 높음 (실제 간선만 저장) |
4. 선택 가이드라인
- 인접 행렬이 유리한 경우:
- 노드 간 연결 상태를 빠르게 확인해야 할 때
- 그래프가 밀집되어 있고 노드 수가 적을 때
- 플로이드-워셜 알고리즘 등 모든 쌍 최단 경로 계산 시
- 인접 리스트가 유리한 경우:
- 메모리 효율이 중요할 때
- 그래프가 희소하고 노드 수가 많을 때
- DFS/BFS 등 탐색 기반 알고리즘 사용 시
- 실제 존재하는 간선만 처리해야 할 때
5. 성능 비교 예시
# 간선 존재 여부 확인
def has_edge_matrix(matrix, u, v):
return matrix[u][v] == 1 # O(1)
def has_edge_list(graph, u, v):
return v in graph[u] # O(k), k는 u의 이웃 수
# 모든 이웃 노드 탐색
def get_neighbors_matrix(matrix, u):
return [i for i, val in enumerate(matrix[u]) if val == 1] # O(V)
def get_neighbors_list(graph, u):
return graph[u] # O(1)
과 간선(edge)으로 구성된 자료구조로, 다양한 관계를 표현하는 데 사용된다. 이 자료구조는 완전 탐색 알고리즘인 DFS, BFS, 백트래킹의 기반이 된다. 파이썬 그래프 완전 정복: 개념·종류·실전 구현){kind=link}