12.3 인접 행렬과 인접 리스트

1. 그래프 표현의 두 주요 방법

그래프를 컴퓨터에서 다루기 위해서는 적절한 자료 구조로 표현해야 한다. 인접 행렬(adjacency matrix)과 인접 리스트(adjacency list)는 가장 널리 사용되는 두 가지 표현 방법이다. 각 방법은 메모리 사용과 연산 효율성에서 다른 균형을 가지며, 응용에 따라 적절한 선택이 필요하다. 본 절에서는 두 표현 방법의 정의, 구현, 비교, 그리고 응용에서의 활용을 자세히 다룬다.

2. 인접 행렬

2.1 정의

그래프 G = (V, E)의 인접 행렬 \mathbf{A}는 |V| \times |V| 크기의 행렬이며, 다음과 같이 정의된다.

A_{ij} = \begin{cases}1 & \text{if } \{v_i, v_j\} \in E \\ 0 & \text{otherwise}\end{cases}

여기서 v_i와 v_j는 노드의 색인이다.

2.2 무방향 그래프의 인접 행렬

무방향 그래프의 인접 행렬은 대칭이다.

A_{ij} = A_{ji}, \quad \forall i, j

이는 \{v_i, v_j\}와 \{v_j, v_i\}가 같은 엣지이기 때문이다.

2.3 방향 그래프의 인접 행렬

방향 그래프의 인접 행렬은 일반적으로 비대칭이다.

A_{ij} = \begin{cases}1 & \text{if } (v_i, v_j) \in E \\ 0 & \text{otherwise}\end{cases}

여기서 (v_i, v_j)는 v_i에서 v_j로의 방향 엣지이다.

2.4 자기 루프

자기 루프(self-loop)가 있는 경우 대각 원소가 1이 된다.

A_{ii} = 1 \quad \text{if } \{v_i, v_i\} \in E

단순 그래프에서는 모든 대각 원소가 0이다.

2.5 가중치 그래프의 인접 행렬

가중치 그래프의 경우 1 대신 가중치 값을 사용한다.

A_{ij} = \begin{cases}w(\{v_i, v_j\}) & \text{if } \{v_i, v_j\} \in E \\ 0 \text{ or } \infty & \text{otherwise}\end{cases}

엣지가 없는 경우의 값(0 또는 무한대)은 응용에 따라 다르다. 최단 경로 알고리즘에서는 일반적으로 무한대를 사용한다.

3. 인접 행렬의 예시

3.1 무방향 그래프

다음과 같은 그래프를 고려하자.

• 노드: \{1, 2, 3, 4\}
• 엣지: \{\{1, 2\}, \{1, 3\}, \{2, 4\}, \{3, 4\}\}

이 그래프의 인접 행렬은 다음과 같다.

\mathbf{A} = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{bmatrix}

행렬이 대칭임을 확인할 수 있다.

3.2 방향 그래프

같은 노드 집합에서 다음의 방향 엣지를 가진 그래프를 고려하자.

• 엣지: \{(1, 2), (1, 3), (2, 4), (4, 3)\}

인접 행렬은 다음과 같다.

\mathbf{A} = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix}

이 행렬은 비대칭이다.

4. 인접 행렬의 구현

4.1 Python에서의 구현

NumPy를 사용한 구현 예시이다.

import numpy as np

# 4개 노드의 무방향 그래프
n = 4
A = np.zeros((n, n), dtype=int)

# 엣지 추가
edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
for u, v in edges:
    A[u][v] = 1
    A[v][u] = 1  # 무방향이므로 대칭

4.2 C++에서의 구현

#include <vector>

const int n = 4;
std::vector<std::vector<int>> A(n, std::vector<int>(n, 0));

// 엣지 추가
A[0][1] = A[1][0] = 1;
A[0][2] = A[2][0] = 1;
// ...

5. 인접 행렬의 연산

5.1 엣지 존재 확인

두 노드 사이에 엣지가 있는지 확인하는 연산은 O(1)이다.

def has_edge(A, u, v):
    return A[u][v] != 0

5.2 이웃 순회

노드의 이웃을 모두 찾는 연산은 O(|V|)이다.

def get_neighbors(A, v):
    return [i for i in range(len(A)) if A[v][i] != 0]

5.3 차수 계산

노드의 차수를 계산하는 연산은 O(|V|)이다.

def degree(A, v):
    return sum(A[v])

5.4 행렬 연산

인접 행렬은 행렬 연산을 직접 적용할 수 있는 장점이 있다.

5.4.1 거듭제곱

\mathbf{A}^k의 (i, j) 원소는 i에서 j로의 길이 k인 경로의 수와 같다.

5.4.2 라플라시안

\mathbf{L} = \mathbf{D} - \mathbf{A}로 그래프 라플라시안을 계산할 수 있다.

5.4.3 스펙트럴 분석

인접 행렬의 고유값과 고유벡터가 그래프의 구조적 성질을 표현한다.

6. 인접 리스트

6.1 정의

인접 리스트는 각 노드에 대해 그 이웃들의 리스트를 저장한다. 일반적으로 다음과 같은 자료 구조로 구현된다.

\text{adj}[v] = [u_1, u_2, \ldots, u_{\deg(v)}]

6.2 무방향 그래프의 인접 리스트

무방향 그래프의 경우 각 엣지가 두 번 저장된다(양 끝 노드의 리스트에 한 번씩).

예시 그래프:

• 노드: \{1, 2, 3, 4\}
• 엣지: \{\{1, 2\}, \{1, 3\}, \{2, 4\}, \{3, 4\}\}

인접 리스트:

1: [2, 3]
2: [1, 4]
3: [1, 4]
4: [2, 3]

6.3 방향 그래프의 인접 리스트

방향 그래프의 경우 각 엣지가 시작 노드의 리스트에만 저장된다.

예시:

• 엣지: \{(1, 2), (1, 3), (2, 4), (4, 3)\}

인접 리스트:

1: [2, 3]
2: [4]
3: []
4: [3]

6.4 가중치 그래프의 인접 리스트

가중치 그래프의 경우 각 이웃과 함께 가중치를 저장한다.

1: [(2, 0.5), (3, 1.2)]
2: [(1, 0.5), (4, 1.5)]
...

7. 인접 리스트의 구현

7.1 Python에서의 구현

딕셔너리를 사용한 구현이 일반적이다.

adj = {i: [] for i in range(n)}

# 엣지 추가
edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)  # 무방향

가중치 그래프의 경우:

adj = {i: [] for i in range(n)}

# 가중 엣지 추가
weighted_edges = [(0, 1, 0.5), (0, 2, 1.2), (1, 3, 1.5)]
for u, v, w in weighted_edges:
    adj[u].append((v, w))
    adj[v].append((u, w))

7.2 C++에서의 구현

#include <vector>

const int n = 4;
std::vector<std::vector<int>> adj(n);

// 엣지 추가
adj[0].push_back(1); adj[1].push_back(0);
adj[0].push_back(2); adj[2].push_back(0);
// ...

가중치 그래프:

std::vector<std::vector<std::pair<int, double>>> adj(n);
adj[0].push_back({1, 0.5});
// ...

8. 인접 리스트의 연산

8.1 엣지 존재 확인

엣지 존재 확인은 O(\deg(v))이다. 노드의 이웃 리스트를 검색해야 한다.

def has_edge(adj, u, v):
    return v in adj[u]

해시 셋을 사용하면 O(1)로 단축할 수 있다.

adj_set = {i: set() for i in range(n)}
# 엣지 추가
adj_set[u].add(v)

def has_edge(adj_set, u, v):
    return v in adj_set[u]  # O(1)

8.2 이웃 순회

이웃 순회는 O(\deg(v))이다. 인접 리스트에서 직접 순회한다.

def get_neighbors(adj, v):
    return adj[v]

8.3 차수 계산

차수 계산은 O(1)이다. 리스트의 길이를 반환한다.

def degree(adj, v):
    return len(adj[v])

9. 두 표현의 비교

9.1 메모리 사용

희소 그래프(|E| \ll |V|^2)에서는 인접 리스트가 훨씬 효율적이다.

9.2 연산 효율성

9.3 응용에 따른 선택

9.3.1 인접 행렬이 적합한 경우

• 밀집 그래프 (|E| = \Theta(|V|^2))
• 엣지 존재 확인이 빈번한 알고리즘
• 행렬 연산이 필요한 알고리즘 (스펙트럴 방법)
• 작은 그래프

9.3.2 인접 리스트가 적합한 경우

• 희소 그래프 (|E| = O(|V|))
• 이웃 순회가 빈번한 알고리즘 (BFS, DFS)
• 큰 그래프
• 그래프가 동적으로 변경되는 경우

10. 가중치 그래프의 표현

10.1 가중치 인접 행렬

가중치 인접 행렬에서 엣지가 없는 경우의 표현이 중요하다.

• 0: 엣지가 없음을 나타내지만, 가중치가 0인 엣지와 구분되지 않는다.
• 무한대: 거리 알고리즘에서 자연스럽다.
• 음수: 일부 응용에서 사용된다.

10.2 가중치 인접 리스트

가중치 인접 리스트는 각 이웃과 가중치의 쌍을 저장한다. 메모리 효율적이며, 모든 경우에 적합하다.

11. 방향성과 가중치의 결합

11.1 방향 가중치 그래프

방향 가중치 그래프는 방향성과 가중치를 모두 가진 그래프이다. 도로 네트워크(일방통행 + 거리), 작업 의존성(우선순위 + 비용) 등에서 사용된다.

11.2 표현

이러한 그래프도 인접 행렬이나 인접 리스트로 표현할 수 있다. 행렬은 비대칭이며, 리스트는 시작 노드에만 엣지가 저장된다.

12. 동적 그래프의 처리

12.1 정적 vs 동적

정적 그래프는 한 번 생성된 후 변경되지 않는다. 동적 그래프는 노드와 엣지가 실행 중에 추가되거나 삭제된다.

12.2 동적 그래프의 표현

동적 그래프에는 인접 리스트가 더 적합하다. 노드와 엣지의 추가/삭제가 효율적이기 때문이다.

12.3 응용

동적 그래프의 응용에는 다음이 있다.

• SLAM에서 로봇이 새 영역을 탐색
• 통신 네트워크의 노드 추가/삭제
• 소셜 네트워크의 사용자 가입/탈퇴

13. 메모리 효율 최적화

13.1 CSR 형식

압축 희소 행(CSR) 형식은 인접 리스트의 메모리 효율을 더욱 향상시킨다. 모든 이웃 리스트를 하나의 큰 배열에 연결해 저장한다.

13.2 비트 행렬

비트 행렬은 인접 행렬을 비트 단위로 압축한다. 메모리를 1/8로 줄일 수 있지만, 비트 연산이 추가된다.

13.3 해시 테이블

엣지를 해시 테이블에 저장하면 평균 O(1)의 엣지 존재 확인이 가능하다. 인접 리스트의 단점을 보완한다.

14. 그래프 표현의 라이브러리 지원

14.1 NetworkX

import networkx as nx

# 무방향 그래프
G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (2, 4)])

# 방향 그래프
DG = nx.DiGraph()

# 가중치 그래프
G.add_edge(1, 2, weight=0.5)

# 인접 행렬과 리스트로 변환
A = nx.adjacency_matrix(G)
adj = nx.to_dict_of_lists(G)

14.2 igraph

import igraph as ig
g = ig.Graph(edges=[(0, 1), (0, 2), (1, 3)])

14.3 다른 라이브러리

• Boost Graph Library (C++)
• LEMON (C++)
• graph-tool (Python)

15. 응용 예시: 격자 그래프

격자 그래프는 모바일 로봇의 경로 계획에서 자주 사용된다. 환경을 격자로 분할하고, 각 셀이 노드, 인접 셀이 엣지로 연결된다.

격자 그래프의 인접성은 함수로 표현할 수 있어, 명시적인 표현이 필요하지 않을 수 있다. 그러나 가중치나 동적 변경이 있으면 명시적 표현이 필요하다.

16. 응용 예시: SLAM 자세 그래프

자세 그래프 SLAM에서 그래프의 노드는 로봇의 자세이고, 엣지는 두 자세 사이의 측정이다. 측정 정보는 평균과 공분산으로 표현된다.

자세 그래프는 일반적으로 희소이며, 인접 리스트가 적합하다. 엣지의 데이터(측정값과 공분산)가 저장된다.

17. 응용 예시: 매니퓰레이터의 운동학

매니퓰레이터의 운동학적 구조는 트리 그래프이다. 각 노드는 링크이고, 엣지는 관절이다. 트리는 매우 작으므로 어떤 표현 방법도 효율적이다.

18. 응용 예시: 도로 네트워크

도로 네트워크는 큰 가중치 그래프이다. 노드는 교차로(수십만~수백만 개), 엣지는 도로 구간이다. 인접 리스트가 메모리 효율과 연산 효율 모두에서 우수하다.

18.1 효율적 구현

도로 네트워크의 효율적 구현에는 다음이 사용된다.

• CSR 형식의 인접 리스트
• 정수 ID 기반 노드 표현
• 압축된 가중치 표현
• 캐시 친화적 데이터 레이아웃

19. 표현의 변환

19.1 인접 행렬에서 인접 리스트로

def matrix_to_list(A):
    n = len(A)
    adj = {i: [] for i in range(n)}
    for i in range(n):
        for j in range(n):
            if A[i][j] != 0:
                adj[i].append(j)
    return adj

19.2 인접 리스트에서 인접 행렬로

def list_to_matrix(adj, n):
    A = [[0] * n for _ in range(n)]
    for u in adj:
        for v in adj[u]:
            A[u][v] = 1
    return A

이러한 변환은 응용에 따라 필요할 수 있다.

20. 학습의 가치

인접 행렬과 인접 리스트를 이해하는 것은 다음과 같은 이점을 제공한다.

• 그래프 자료 구조의 기본을 익힌다.
• 응용에 적합한 표현을 선택할 수 있다.
• 알고리즘의 효율성을 분석할 수 있다.
• 그래프 라이브러리를 효과적으로 사용할 수 있다.

21. 학습 권장사항

21.1 직접 구현

두 표현 방법을 직접 구현해 보는 것이 이해에 도움이 된다. 각 연산의 효율성을 측정해 본다.

21.2 비교 실험

같은 그래프에 대해 두 표현 방법의 메모리 사용과 연산 시간을 비교해 본다.

21.3 실제 응용

NetworkX나 igraph 등의 라이브러리를 사용하여 실제 응용을 다루어 본다.

22. 본 절의 의의

본 절은 그래프 표현의 두 핵심 방법을 자세히 다루었다. 인접 행렬과 인접 리스트는 후속 알고리즘 학습의 기반이며, 응용에 따른 적절한 선택이 알고리즘의 성능을 좌우한다.

23. 참고 문헌

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
• Skiena, S. S. (2008). The Algorithm Design Manual (2nd ed.). Springer.
• Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley.
• Hagberg, A. A., Schult, D. A., & Swart, P. J. (2008). “Exploring network structure, dynamics, and function using NetworkX.” Proceedings of the 7th Python in Science Conference, 11–15.

version: 1.0