인접 행렬

인접 행렬은 그래프 이론에서 그래프의 정점들 간의 연결 관계를 행렬 형태로 표현한 자료구조이다. 주로 그래프 표현이나 그래프 알고리즘 구현, 네트워크 분석 등에 활용된다.

이 표현 방식은 2차원 배열을 사용하며, 정점 i에서 정점 j로의 간선 존재 여부를 행렬의 (i, j) 원소 값으로 표시한다. 이를 통해 방향 그래프와 무방향 그래프를 모두 표현할 수 있으며, 가중치 그래프의 경우 간선의 가중치를 행렬 값에 직접 저장할 수 있다.

인접 행렬의 주요 특징 중 하나는 두 정점 사이에 특정 간선이 존재하는지 여부를 상수 시간(O(1))에 확인할 수 있다는 점이다. 이는 행렬의 해당 위치를 직접 참조하기만 하면 되기 때문이다.

인접 행렬은 그래프 이론에서 그래프의 정점들 간의 연결 관계를 행렬 형태로 표현한 자료구조이다. 이 표현 방식은 주로 그래프 알고리즘을 구현하거나 네트워크 분석을 수행할 때 활용된다.

구체적으로, 정점의 개수가 n개인 그래프를 표현하기 위해 n x n 크기의 2차원 배열을 사용한다. 이 행렬에서 i번째 행과 j번째 열에 위치한 원소의 값은 정점 i에서 정점 j로 향하는 간선의 존재 여부 또는 그 정보를 나타낸다. 가장 기본적인 형태에서는 간선이 존재하면 1, 존재하지 않으면 0과 같은 값을 저장하여 연결 상태를 표시한다.

이 방식은 방향 그래프와 무방향 그래프를 모두 표현할 수 있다. 무방향 그래프의 경우, 간선이 대칭적이므로 인접 행렬도 대칭 행렬이 된다. 또한 가중치 그래프를 표현할 때는 행렬의 각 원소에 간선의 가중치 값을 직접 저장할 수 있으며, 간선이 없는 경우에는 0이나 무한대(∞)와 같은 특별한 값으로 표시한다.

인접 행렬의 가장 큰 장점 중 하나는 두 정점 사이에 특정 간선이 존재하는지 여부를 상수 시간(O(1))에 확인할 수 있다는 점이다. 행렬의 (i, j) 위치에 접근하는 것만으로 즉시 연결 정보를 얻을 수 있어, 간선의 존재를 빈번히 확인해야 하는 알고리즘에 유리하다.

인접 행렬을 사용할 때의 시간 복잡도는 수행하는 연산에 따라 다르다. 가장 큰 장점은 두 정점 사이에 간선이 존재하는지 확인하는 연산의 시간 복잡도가 O(1)이라는 점이다. 이는 행렬의 특정 인덱스에 직접 접근하여 값을 확인하면 되기 때문이다.

그러나 특정 정점에 연결된 모든 이웃 정점을 찾는 연산은 O(V)의 시간이 소요된다. V는 정점의 개수로, 행렬에서 해당 정점의 행이나 열 전체를 순회해야 하기 때문이다. 마찬가지로 그래프에 존재하는 모든 간선을 나열하는 작업도 O(V^2)의 시간이 걸린다. 이는 2차원 배열의 모든 원소를 확인해야 하기 때문이다.

그래프 순회 알고리즘인 깊이 우선 탐색이나 너비 우선 탐색을 인접 행렬로 구현할 경우, 각 정점의 이웃을 찾는 데 O(V) 시간이 걸리므로 전체 시간 복잡도는 O(V^2)이 된다. 이는 인접 리스트 표현을 사용했을 때의 O(V+E) 복잡도보다 일반적으로 비효율적이다. 여기서 E는 간선의 개수를 의미한다.

인접 행렬의 공간 복잡도는 그래프의 정점 수에 따라 결정된다. 정점이 V개인 그래프의 인접 행렬은 V x V 크기의 2차원 배열로 표현되므로, 필요한 총 공간은 V의 제곱에 비례한다. 이는 정점 간의 실제 간선 수와 무관하게 항상 V^2개의 원소를 저장해야 함을 의미한다.

따라서 인접 행렬의 공간 복잡도는 O(V^2)이다. 이는 밀집 그래프처럼 간선이 많은 경우에는 효율적일 수 있지만, 희소 그래프처럼 실제 간선 수가 적은 경우에는 메모리 낭비가 발생할 수 있는 구조적 특징이다. 이러한 공간 사용 특성은 인접 리스트와 비교되는 주요 차이점 중 하나이다.

인접 행렬은 그래프 이론과 알고리즘 구현에서 널리 사용되는 기본적인 자료구조이다. 그 직관적인 구조 덕분에 다양한 컴퓨터 과학 및 응용 분야에서 그래프를 표현하고 분석하는 핵심 도구로 활용된다.

주요 응용 분야로는 그래프 알고리즘의 구현이 있다. 플로이드-워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 찾는 대표적인 알고리즘으로, 중간 정점을 거치는 모든 가능성을 체계적으로 검토하기 위해 인접 행렬을 직접적으로 사용하며 갱신한다. 또한 너비 우선 탐색이나 깊이 우선 탐색과 같은 기본적인 그래프 순회 알고리즘에서도 정점 간 연결 상태를 빠르게 확인하는 데 유용하게 쓰인다.

네트워크 분석 분야에서도 인접 행렬은 중요한 역할을 한다. 소셜 네트워크에서 사용자 간의 친구 관계, 통신 네트워크에서 장치 간의 연결 상태, 혹은 교통 네트워크에서 도시 간의 도로 연결을 행렬로 표현하면 네트워크의 구조적 특성을 수학적으로 분석하기 용이하다. 이를 통해 연결 중심성이나 군집 계수 같은 네트워크 지표를 계산할 수 있다.

이외에도 게임 이론에서 플레이어 간의 상호작용 모델링, 컴파일러 설계에서 제어 흐름 그래프 표현, 로보틱스에서 환경 지도 생성 및 경로 계획 등 다양한 분야에서 그래프를 표현하는 표준적인 방법으로 인접 행렬이 채택되고 있다.

인접 행렬은 2차원 배열을 사용하여 구현한다. 정점의 개수를 n이라고 할 때, n x n 크기의 행렬을 생성하고, 각 행과 열은 정점에 대응된다. 행렬의 원소는 일반적으로 정수형 변수로 선언하며, 간선이 존재하지 않음을 나타내는 특정 값(예: 0 또는 무한대)으로 초기화한다.

다음은 인접 행렬을 사용한 기본적인 그래프 연산의 의사 코드 예시이다. 여기서는 정점 번호가 0부터 n-1까지라고 가정한다.

구체적인 프로그래밍 언어에 따른 구현은 다를 수 있으나, 핵심은 모든 정점 쌍에 대한 연결 정보를 상수 시간에 접근할 수 있는 자료 구조를 구성하는 것이다. 이 구조는 플로이드-워셜 알고리즘과 같이 모든 정점 쌍의 관계를 계산해야 하는 알고리즘에 적합하다.

인접 행렬과 인접 리스트는 그래프를 표현하는 대표적인 두 가지 자료구조이다. 각 방식은 장단점이 명확히 구분되어 주어진 문제의 특성에 따라 선택해야 한다.

인접 행렬은 모든 정점 쌍에 대한 연결 여부를 상수 시간에 확인할 수 있어 간선 검색이 빈번한 알고리즘에 유리하다. 또한 구현이 직관적이고 밀집 그래프를 표현할 때 공간 낭비가 상대적으로 적다. 반면, 정점 수가 많고 간선이 적은 희소 그래프에서는 대부분의 행렬 원소가 사용되지 않아 메모리 효율이 매우 떨어진다.

인접 리스트는 각 정점에 연결된 간선만을 리스트로 관리하여 희소 그래프를 표현할 때 공간 효율이 극대화된다. 또한 한 정점에 연결된 모든 이웃을 탐색하는 데 걸리는 시간이 해당 정점의 차수에 비례하므로, 깊이 우선 탐색이나 너비 우선 탐색과 같은 그래프 순회 알고리즘에서 일반적으로 더 빠른 성능을 보인다. 다만, 두 특정 정점 사이에 간선이 존재하는지 확인하려면 리스트를 순차 탐색해야 할 수 있다는 단점이 있다.

따라서 그래프 알고리즘을 선택할 때는 그래프의 밀도, 수행할 연산의 종류(예: 간선 조회 vs. 이웃 순회), 그리고 메모리 제약 등을 종합적으로 고려하여 적절한 자료구조를 결정해야 한다.

[2]: 연결 리스트 기반 구현 시 간선 추가는 O(1), 삭제는 탐색 시간이 추가로 소요될 수 있다.

• 위키백과 - 그래프 이론

• 위키백과 - 인접 리스트

• 위키백과 - 그래프 (자료 구조)

• 위키백과 - 희소 행렬

• 위키백과 - 가중치 그래프

• GeeksforGeeks - Graph and its representations

• Khan Academy - Representing graphs