그래프 이론에서의 인접 시(Adjacency)

그래프 이론에서의 인접 시(Adjacency)

정의

그래프의 인접 시(adjacency)는 두 정점이 직접 연결되어 있는지를 나타내는 방법입니다. 이를 위해 여러가지 자료구조를 사용할 수 있는데, 인접 리스트(Adjacency List), 인접 행렬(Adjacency Matrix), 인접 다중집합(Adjacency Multiset) 등이 있습니다.

특징

1. 표현 방법: 인접 행렬은 2차원 배열을, 인접 리스트는 리스트나 연결 리스트를 사용합니다.
2. 공간 복잡도: 인접 행렬은 (O(V^2)), 인접 리스트는 (O(V + E))의 공간을 차지합니다.
3. 시간 복잡도: 두 정점이 인접한지 확인하는 데에는 인접 행렬이 (O(1))이지만, 인접 리스트는 최악의 경우 (O(V))입니다.

사용 예

1. 소셜 네트워크 분석: 친구 관계나 팔로우 관계를 나타낼 때
2. 경로 찾기 알고리즘: 다양한 경로 찾기 알고리즘에서 그래프를 표현할 때
3. 플로우 네트워크: 유량을 최대화하는 경로를 찾을 때

C와 Python에서의 비교

C

C에서는 인접 리스트를 연결 리스트로, 인접 행렬을 2차원 배열로 구현할 수 있습니다. 메모리를 명시적으로 관리해야 하며, 복잡한 연산을 수행할 때는 자료구조를 직접 구현해야 할 수도 있습니다.

// 인접 리스트 예시
struct Node {
    int vertex;
    struct Node* next;
};
// ...

// 인접 행렬 예시
int adjacency_matrix[V][V];
// ...

Python

Python에서는 인접 리스트를 내장 리스트나 딕셔너리로, 인접 행렬을 2차원 리스트로 쉽게 구현할 수 있습니다. 또한, 표준 라이브러리를 활용하여 더 편리하게 그래프를 조작할 수 있습니다.

# 인접 리스트 예시
adjacency_list = {'A': ['B', 'C'], 'B': ['D'], 'C': [], 'D': []}

# 인접 행렬 예시
adjacency_matrix = [
    [0, 1, 1, 0],
    [0, 0, 0, 1],
    [0, 0, 0, 0],
    [0, 0, 0, 0]
]

정리

C언어는 성능과 메모리를 더 세밀하게 관리할 수 있지만, 구현이 복잡하고 디버깅이 어려울 수 있습니다. Python은 간결하고 직관적인 문법으로 빠르게 구현할 수 있지만, 성능에 제약이 있을 수 있습니다.