그래프 이론 - 2. 그래프 표현 방법

2. 그래프 표현 방법

2.1 인접 행렬(Adjacency Matrix)

📌 정의 및 구현

인접 행렬은 정점 간의 연결을 2차원 배열(행렬)로 표현하는 방법입니다.

📌 무방향 그래프 (비가중치)

  A --- B
   \   /
    C

이 그래프를 인접 행렬로 나타내면 다음과 같습니다.

	A	B	C
A	0	1	1
B	1	0	1
C	1	1	0

📌 가중치 그래프 (Weighted Graph)

  A --(2)--> B
   \-(5)-→ C

이 경우, 가중치를 행렬에 저장합니다.

	A	B	C
A	0	2	5
B	0	0	0
C	0	0	0

---

📌 인접 행렬 구현 (Python)

# 그래프 정의 (가중 방향 그래프)
N = 3  # 정점 개수
adj_matrix = [[0] * N for _ in range(N)]  # N x N 2차원 배열 초기화

# 간선 추가 (A=0, B=1, C=2)
adj_matrix[0][1] = 2  # A → B (가중치 2)
adj_matrix[0][2] = 5  # A → C (가중치 5)

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

📌 출력 결과

[0, 2, 5]
[0, 0, 0]
[0, 0, 0]

---

2.2 인접 리스트(Adjacency List)

📌 정의 및 구현

각 정점마다 연결된 정점들을 리스트로 관리하는 방식입니다.

📌 무방향 그래프 (비가중치)

  A --- B
   \   /
    C

A: [B, C]
B: [A, C]
C: [A, B]

📌 가중 방향 그래프 (Weighted Graph)

  A --(3)--> B
   \-(2)-→ C

A: [(B, 3), (C, 2)]
B: []
C: []

---

📌 인접 리스트 구현 (Python)

(1) 기본 딕셔너리(dict) 사용

# 기본 딕셔너리로 인접 리스트 구현
graph = {}

# 정점 추가
graph[0] = [1, 2]  # A → B, A → C
graph[1] = []  # B는 아무것도 연결되지 않음
graph[2] = []  # C도 연결 없음

# 출력
for node, edges in graph.items():
    print(f"{node}: {edges}")

📌 출력 결과

0: [1, 2]
1: []
2: []

(2) defaultdict 사용 (더 유연한 방식)

from collections import defaultdict

# defaultdict를 사용한 인접 리스트 구현
graph = defaultdict(list)

# 간선 추가 (A=0, B=1, C=2)
graph[0].append((1, 3))  # A → B (가중치 3)
graph[0].append((2, 2))  # A → C (가중치 2)

# 리스트 출력
for node, edges in graph.items():
    print(f"{node}: {edges}")

📌 출력 결과

0: [(1, 3), (2, 2)]
1: []
2: []

---

 

✅ 최종 비교: 그래프 표현 방법 정리

표현 방식	저장 구조	메모리 사용	두 정점 간 연결 여부 확인	연결된 정점 탐색 속도	구현 난이도	추천 상황
인접 행렬	2차원 배열	𝑂(𝑁²)	𝑂(1) (빠름)	𝑂(𝑁) (느림)	쉬움	Dense Graph (간선이 많은 그래프)
인접 리스트	리스트의 배열	𝑂(𝑁+E)	𝑂(𝑁) (느림)	𝑂(정점 차수) (빠름)	보통	Sparse Graph (간선이 적은 그래프)