인접 행렬(Adjacency Matrix)의 정의와 특징

인접 행렬(Adjacency Matrix)의 정의와 특징

정의

인접 행렬은 그래프의 정점들 간의 연결 관계를 2차원 배열로 표현한 것입니다. 행렬의 (i)-행, (j)-열의 원소는 (i)번째 정점과 (j)번째 정점이 연결되어 있으면 1, 아니면 0으로 표시합니다. 가중치가 있는 그래프의 경우, 해당 원소에 가중치 값을 저장할 수 있습니다.

특징

1. 고정된 공간 복잡도: (O(V^2))의 공간이 필요합니다.
2. 직접적인 조회: 두 정점이 인접한지 확인하는 시간 복잡도는 (O(1))입니다.
3. 간선 추가/삭제 비용: (O(1))의 시간 복잡도로 간선을 추가하거나 삭제할 수 있습니다.
4. 자료구조 간단: 구현이 간단하고 이해하기 쉽습니다.

사용 예

1. 희소 그래프가 아닌 경우: 정점의 수에 비해 간선이 많을 때 효율적입니다.
2. 가중치가 있는 그래프: 가중치 정보를 쉽게 저장할 수 있습니다.
3. 그래프 알고리즘: 플로이드-와샬 알고리즘과 같은 알고리즘에서 자주 사용됩니다.

C와 Python에서의 비교

C

C에서 인접 행렬은 보통 2차원 배열로 구현됩니다. 동적 할당을 사용하여 크기를 지정할 수 있으며, 메모리 관리가 수동적입니다.

int adjacency_matrix[5][5] = {
    {0, 1, 0, 0, 1},
    {1, 0, 1, 1, 1},
    {0, 1, 0, 1, 0},
    {0, 1, 1, 0, 1},
    {1, 1, 0, 1, 0}
};

Python

Python에서는 2차원 리스트를 사용하여 인접 행렬을 쉽게 구현할 수 있습니다. 동적 타이핑과 내장 함수를 활용하여 더 간결하게 코드를 작성할 수 있습니다.

adjacency_matrix = [
    [0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1],
    [0, 1, 0, 1, 0],
    [0, 1, 1, 0, 1],
    [1, 1, 0, 1, 0]
]

정리

C언어에서는 메모리와 성능을 더 세밀하게 컨트롤할 수 있지만, 구현이 상대적으로 복잡할 수 있습니다. Python은 간결한 문법과 라이브러리를 통해 빠르고 쉬운 구현을 가능하게 합니다, 하지만 성능상의 제약이 있을 수 있습니다.

---

인접 행렬(Adjacency Matrix)로 표현된 그래프의 정의와 특징