그래프는 정점과 간선의 집합으로 구성된 추상적인 자료 구조이다. 컴퓨터 과학에서 그래프는 객체들 간의 관계나 연결을 모델링하는 데 널리 사용된다. 예를 들어, 소셜 네트워크에서 사람들은 정점으로, 친구 관계는 간선으로 표현될 수 있다.
그래프를 컴퓨터 프로그램에서 처리하려면 이를 적절한 자료 구조로 표현해야 한다. 가장 일반적인 두 가지 표현 방식은 인접 행렬과 인접 리스트이다. 인접 행렬은 2차원 배열을 사용하여 모든 정점 쌍 사이의 연결 관계를 명시적으로 저장한다. 반면, 인접 리스트는 각 정점마다 연결된 이웃 정점들의 목록을 동적으로 관리한다.
이 두 표현법은 메모리 사용량과 다양한 연산(예: 특정 간선 존재 확인, 모든 이웃 탐색)의 효율성에서 서로 다른 특성을 보인다. 따라서 그래프의 밀도(간선의 수), 필요한 연산의 종류, 그리고 사용 가능한 메모리 등의 요인에 따라 적절한 표현 방식을 선택하는 것이 중요하다.
본 문서는 그래프의 기본 개념을 설명하고, 인접 행렬과 인접 리스트의 구조, 장단점, 시간 복잡도를 상세히 분석한다. 또한 두 방식을 비교하고, 깊이 우선 탐색 및 너비 우선 탐색과 같은 기본 알고리즘을 각 표현법으로 어떻게 구현하는지 살펴본다.
그래프는 정점과 간선의 집합으로 구성된 추상적인 자료 구조이다. 정점은 객체나 개체를 나타내고, 간선은 이들 사이의 관계나 연결을 표현한다. 그래프는 네트워크 구조, 지도 상의 위치 관계, 소셜 네트워크의 친구 관계 등 다양한 현실 세계의 문제를 모델링하는 데 널리 사용된다.
정점은 보통 V나 Node로 표기하며, 그래프의 기본 단위이다. 간선은 두 정점을 연결하며, E나 Edge로 표기한다. 간선은 연결하는 두 정점의 쌍 (u, v)로 정의된다. 간선의 종류에 따라 그래프는 크게 무방향 그래프와 방향 그래프로 나뉜다. 무방향 그래프에서 간선 (u, v)는 정점 u와 v가 서로 연결되어 있음을 의미하며, 순서가 없다. 방향 그래프(유향 그래프)에서는 간선 (u, v)가 u에서 v로의 방향성을 가지며, 이 경우 (u, v)와 (v, u)는 서로 다른 간선이다.
또한, 간선에 추가적인 수치 정보가 부여될 수 있는데, 이를 가중치라고 한다. 가중치가 있는 그래프를 가중 그래프라 부른다. 가중치는 두 지점 사이의 거리, 이동 시간, 연결 비용, 관계의 강도 등을 나타내는 데 사용된다. 반면, 모든 간선의 가중치가 동일하거나 무시되는 그래프는 비가중 그래프로 분류된다.
그래프는 정점과 간선의 집합으로 구성된 자료 구조이다. 정점은 그래프의 기본 구성 요소로, 객체나 개체를 나타낸다. 간선은 두 정점 사이의 연결 관계를 표현한다.
정점은 보통 V로 표시되며, 각 정점은 고유한 식별자(예: 번호나 이름)로 구분된다. 간선은 보통 E로 표시되며, 두 정점의 쌍 (u, v)으로 정의된다. 간선의 종류에 따라 그래프는 무방향 그래프와 방향 그래프로 나뉜다. 무방향 그래프에서 간선 (u, v)는 정점 u와 v가 서로 연결되어 있음을 의미하며, 방향 그래프에서 간선 (u, v)는 u에서 v로의 단방향 연결을 의미한다.
용어 | 설명 | 비고 |
|---|---|---|
그래프의 기본 노드. 객체를 나타냄. | Vertex, Node라고도 함. | |
두 정점 간의 연결 관계. | Edge, Link, Arc라고도 함. | |
한 정점에 연결된 간선의 수. |
정점과 간선의 개념은 네트워크, 지도, 소셜 미디어 관계 등 다양한 현실 세계의 문제를 추상화하는 데 사용된다. 예를 들어, 소셜 네트워크에서 사람은 정점이 되고, 친구 관계는 간선이 된다.
그래프는 간선에 방향성이 존재하는지 여부에 따라 방향 그래프와 무방향 그래프로 구분된다. 방향 그래프에서는 간선이 한 정점에서 다른 정점으로의 방향을 가지며, (u, v)와 (v, u)는 서로 다른 간선으로 취급된다. 반면 무방향 그래프에서는 간선이 양방향 연결을 의미하며, (u, v)와 (v, u)는 동일한 간선이다.
간선에 추가적인 수치 정보가 부여된 그래프를 가중 그래프라고 한다. 이때 부여된 값을 가중치라고 하며, 이는 거리, 비용, 시간, 용량 등 다양한 의미를 가질 수 있다. 가중치가 없는 그래프는 비가중 그래프로, 모든 간선의 가중치가 동일한 것으로 간주된다.
방향성과 가중치의 조합에 따라 그래프는 네 가지 주요 유형으로 분류될 수 있다.
그래프 유형 | 방향성 | 가중치 | 예시 |
|---|---|---|---|
무방향 비가중 그래프 | 없음 | 없음 | 소셜 네트워크의 친구 관계 |
무방향 가중 그래프 | 없음 | 있음 | 도로 네트워크(거리) |
방향 비가중 그래프 | 있음 | 없음 | 웹페이지 간 하이퍼링크 |
방향 가중 그래프 | 있음 | 있음 | 항공 노선(비용, 시간) |
이러한 특성은 그래프를 표현하는 인접 행렬이나 인접 리스트의 구조와 사용되는 알고리즘의 선택에 직접적인 영향을 미친다. 예를 들어, 방향 그래프의 인접 행렬은 대칭적이지 않을 수 있으며, 가중 그래프의 경우 행렬 셀이나 리스트 노드에 가중치 값을 저장해야 한다.
인접 행렬은 그래프의 연결 관계를 정방형 행렬로 표현하는 방법이다. 행렬의 행과 열은 각각 그래프의 정점에 대응된다. 일반적으로 정점의 개수를 V라고 할 때, V x V 크기의 2차원 배열을 사용한다.
행렬의 요소 M[i][j]는 정점 i와 정점 j 사이의 관계를 나타낸다. 무방향 그래프의 경우, 두 정점 사이에 간선이 존재하면 M[i][j]와 M[j][i]를 모두 1로 설정한다. 이는 행렬이 주대각선을 기준으로 대칭이 됨을 의미한다. 방향 그래프에서는 간선의 방향에 따라 M[i][j]만 1로 설정한다. 가중 그래프에서는 1 대신 해당 간선의 가중치를 저장한다.
인접 행렬 표현법의 주요 장점은 특정 두 정점 사이의 연결 존재 여부를 상수 시간, 즉 O(1)에 확인할 수 있다는 점이다. 또한 구현이 직관적이고 간단하다. 그러나 단점은 메모리 공간을 O(V²)만큼 사용한다는 것이다. 이는 간선의 수가 적은 희소 그래프에서 많은 공간이 낭비될 수 있음을 의미한다. 전체 간선을 탐색하려면 V²번의 순회가 필요해, 간선 수에 비해 비효율적일 수 있다.
연산 | 시간 복잡도 | 설명 |
|---|---|---|
두 정점 연결 확인 | O(1) | 배열 접근 한 번으로 가능 |
정점의 모든 인접 정점 나열 | O(V) | 해당 행 또는 열을 전체 탐색 |
간선 추가/삭제 | O(1) | 해당 배열 요소 값 변경 |
전체 구조 저장 공간 | O(V²) | V가 정점의 개수 |
따라서 인접 행렬은 정점 간 연결 관계를 빈번히 확인해야 하거나, 밀집 그래프처럼 간선의 수가 V²에 가까운 경우에 효율적이다.
인접 행렬은 2차원 배열을 사용하여 그래프의 연결 관계를 표현한다. 행렬의 행과 열은 각각 그래프의 정점에 대응하며, 행렬의 요소 M[i][j]는 정점 i에서 정점 j로의 간선 존재 여부 또는 그 가중치를 나타낸다.
무방향 그래프의 경우, 행렬은 주대각선을 기준으로 대칭 구조를 가진다. 즉, M[i][j]와 M[j][i]의 값이 항상 동일하다. 가중치가 없는 그래프에서는 간선이 존재할 경우 1, 존재하지 않을 경우 0을 저장한다. 가중 그래프의 경우, 간선의 가중치 값을 직접 저장하고, 간선이 없음을 나타내는 값으로 0, 무한대(INF), 또는 null과 같은 특수 값을 사용한다[1].
반면, 인접 리스트는 각 정점마다 연결된 다른 정점들의 목록을 개별적으로 관리하는 방식이다. 일반적으로 배열 또는 연결 리스트의 배열로 구현되며, 배열의 인덱스 i가 정점 i를 가리키고, 그 요소는 정점 i에 인접한 모든 정점의 목록이 된다.
인접 리스트의 각 노드는 연결된 정점의 식별자와, 가중 그래프일 경우 추가로 가중치 정보를 저장한다. 이 표현법은 실제 존재하는 간선에 대해서만 메모리를 할당하므로, 간선이 적은 희소 그래프에서 효율적이다. 구현 방식에 따라 동적 배열(ArrayList, Vector)이나 연결 리스트(LinkedList)를 사용할 수 있으며, 이 선택은 특정 연산(예: 간선 추가/삭제, 순회)의 빈도에 따라 성능에 영향을 미친다.
인접 행렬의 가장 큰 장점은 두 정점 사이의 연결 관계를 상수 시간, 즉 O(1)에 확인할 수 있다는 점이다. matrix[i][j] 값을 조회하는 것만으로 정점 i와 j의 연결 여부와 가중치를 즉시 알 수 있다. 또한, 밀집 그래프를 표현할 때 메모리 효율이 상대적으로 좋으며, 구현이 직관적이고 간단하다. 그래프의 전체 구조를 한눈에 파악하기 쉬운 장점도 있다.
주요 단점은 메모리 공간의 낭비가 발생할 수 있다는 것이다. 정점의 개수를 V라고 할 때, V² 크기의 행렬이 필요하며, 희소 그래프의 경우 대부분의 공간이 0이나 null 값으로 채워져 비효율적이다. 또한, 특정 정점에 연결된 모든 이웃 정점을 찾는 연산은 O(V)의 시간이 소요되어 비효율적일 수 있다. 그래프에 새로운 정점을 추가하거나 삭제하는 작업도 행렬 크기를 재조정해야 하므로 복잡하다.
인접 리스트의 가장 큰 장점은 메모리 사용이 효율적이라는 것이다. 실제 존재하는 간선만 저장하므로, 희소 그래프에서 인접 행렬에 비해 훨씬 적은 메모리를 사용한다. 또한, 한 정점에 연결된 모든 인접 정점을 탐색하는 데 매우 효율적이다. 정점 V의 차수(degree)가 d라면, 이 연산은 O(d) 시간에 수행된다. 그래프의 동적 변경, 즉 정점이나 간선의 추가 및 삭제도 비교적 용이하다.
주요 단점은 두 정점이 직접 연결되어 있는지 확인하는 데 O(d) 시간이 걸린다는 것이다. 최악의 경우(정점의 차수가 높은 경우) 이는 O(V)에 근접할 수 있다. 또한, 인접 행렬에 비해 구현이 다소 복잡하며, 간선에 가중치를 저장하려면 추가적인 데이터 구조가 필요하다. 밀집 그래프에서 간선의 개수가 V²에 가까워지면, 리스트를 관리하는 오버헤드로 인해 오히려 인접 행렬보다 비효율적일 수 있다.
인접 행렬 표현에서 주요 연산의 시간 복잡도는 정점의 수 V에 크게 의존한다. 특정 두 정점 사이에 간선이 존재하는지 확인하는 연산은 행렬의 해당 인덱스를 직접 참조하면 되므로 O(1)의 상수 시간에 수행된다. 모든 정점에 대한 특정 정점의 이웃을 찾는 연산은 행렬의 한 행 또는 한 열을 모두 검사해야 하므로 O(V)의 시간이 소요된다. 새로운 간선을 추가하거나 삭제하는 연산 역시 행렬의 특정 셀 값을 갱신하면 되므로 O(1)의 시간 복잡도를 가진다. 그러나 정점을 추가하려면 행렬의 크기를 재할당하고 모든 값을 복사해야 할 수 있어 O(V^2)의 비용이 발생할 수 있다.
인접 리스트 표현의 시간 복잡도는 정점의 수 V와 간선의 수 E에 따라 결정된다. 두 정점 간의 간선 존재 여부를 확인하려면 한 정점의 연결 리스트를 선형 검색해야 하므로, 최악의 경우 O(degree(V)) 시간이 걸린다. 여기서 degree(V)는 해당 정점의 차수이다. 밀집 그래프에서는 이 값이 O(V)에 가까울 수 있다. 반면, 특정 정점의 모든 이웃을 순회하는 연산은 해당 리스트를 따라가면 되므로 O(degree(V)) 시간이 소요된다. 이는 일반적으로 인접 행렬의 O(V)보다 효율적이다. 간선을 추가하는 연산은 리스트의 맨 앞에 노드를 삽입하는 방식으로 O(1)에 가능하지만, 간선 삭제는 리스트 검색이 필요하므로 O(degree(V)) 시간이 걸린다.
연산 | 인접 행렬 | 인접 리스트 |
|---|---|---|
간선 존재 확인 |
|
|
정점의 모든 이웃 순회 |
|
|
간선 추가 |
|
|
간선 삭제 |
|
|
공간 복잡도 |
|
|
따라서, 간선 검색이 빈번한 응용에는 인접 행렬이, 그래프 순회나 이웃 탐색이 주를 이루는 알고리즘에는 인접 리스트가 일반적으로 더 유리한 시간적 특성을 보인다.
인접 리스트는 그래프를 표현하는 방법 중 하나로, 각 정점마다 그 정점에 인접한(연결된) 다른 정점들의 목록을 저장하는 방식이다. 각 정점은 일반적으로 연결 리스트나 동적 배열을 사용하여 자신과 직접 연결된 이웃 정점들을 관리한다. 예를 들어, 정점 A가 정점 B와 C와 연결되어 있다면, A의 인접 리스트에는 B와 C에 대한 참조(또는 식별자)가 저장된다. 방향 그래프의 경우, 간선의 방향에 따라 리스트에 포함되는 정점이 달라진다. 즉, 정점 V에서 나가는 간선의 목적지만을 V의 인접 리스트에 저장한다.
인접 리스트 표현법의 주요 장점은 메모리 사용 효율성이 높다는 점이다. 필요한 저장 공간은 정점의 수(V)와 간선의 수(E)에 비례하여 O(V + E)이다. 이는 희소 그래프(간선의 수가 적은 그래프)에서 특히 유리하다. 또한, 특정 정점에 연결된 모든 이웃 정점들을 순회하는 작업은 매우 효율적이다. 단점은 두 정점 사이에 특정 간선이 존재하는지 확인하는 데 O(degree(V))의 시간이 걸릴 수 있다는 것이다. 여기서 degree(V)는 해당 정점의 차수(연결된 간선 수)를 의미한다. 최악의 경우(완전 그래프에 가까울 때) 이는 O(V)에 달할 수 있다.
연산 | 시간 복잡도 (평균) | 설명 |
|---|---|---|
간선 존재 여부 확인 | O(degree(V)) | 해당 정점의 인접 리스트를 선형 검색해야 함 |
모든 이웃 정점 순회 | O(degree(V)) | 리스트를 처음부터 끝까지 읽으면 됨 |
간선 추가 | O(1) (또는 O(log n)[3]) | 리스트의 맨 앞이나 뒤에 새 노드를 추가 |
간선 삭제 | O(degree(V)) | 리스트에서 해당 노드를 검색하여 삭제 |
저장 공간 | O(V + E) | 정점 수와 간선 수에 비례 |
인접 리스트는 깊이 우선 탐색(DFS)이나 너비 우선 탐색(BFS)처럼 그래프 전체를 순회하거나, 특정 정점의 이웃을 빠르게 탐색해야 하는 알고리즘에 적합하다. 반면, 간선의 존재를 빈번히 확인해야 하는 알고리즘에는 비효율적일 수 있다.
인접 행렬은 2차원 배열을 사용하여 그래프의 연결 관계를 표현하는 방법이다. 행과 열 모두 정점에 대응되며, 행렬의 각 요소는 두 정점 사이의 간선 존재 여부 또는 가중치를 나타낸다.
무방향 그래프의 경우, 행렬은 주대각선을 기준으로 대칭 구조를 가진다. 정점 i와 정점 j 사이에 간선이 존재하면, matrix[i][j]와 matrix[j][i]의 값을 1(또는 가중치)로 설정한다. 가중치가 없는 그래프에서는 일반적으로 간선이 있으면 1, 없으면 0으로 표시한다. 가중 그래프의 경우, 해당 위치에 가중치 값을 저장하고, 간선이 없음을 나타내는 값(예: 0, 무한대, 또는 -1)을 사용한다.
정점 | A | B | C | D |
|---|---|---|---|---|
A | 0 | 1 | 1 | 0 |
B | 1 | 0 | 0 | 1 |
C | 1 | 0 | 0 | 1 |
D | 0 | 1 | 1 | 0 |
위 표는 A-B, A-C, B-D, C-D로 연결된 무방향 그래프의 인접 행렬 예시이다. 대각선은 보통 자기 자신으로의 연결(루프)이 없으므로 0으로 채워진다.
인접 리스트는 각 정점마다 연결된 다른 정점들의 목록을 개별적으로 관리하는 방식이다. 각 정점을 인덱스로 하는 배열을 만들고, 각 배열 요소는 해당 정점에 인접한 정점들의 연결 리스트나 동적 배열을 가리킨다. 이 방식은 실제 존재하는 간선만을 저장한다.
같은 그래프를 인접 리스트로 표현하면 다음과 같은 구조가 된다.
A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]
가중 그래프를 표현할 때는 리스트의 각 노드가 (연결된 정점, 가중치)의 쌍으로 구성된다. 방향 그래프의 경우, 나가는 간선만을 저장하는 것이 일반적이며, 들어오는 간선을 알고 싶다면 역인접 리스트를 별도로 구성할 수 있다.
인접 행렬의 주요 장점은 두 정점 사이의 연결 관계를 상수 시간, 즉 O(1)에 확인할 수 있다는 점이다. 특정 간선의 존재 여부나 가중치를 조회하는 연산이 매우 빠르다. 또한 구현이 직관적이고 간단하여 코드 작성이 용이하다. 완전 그래프와 같이 간선의 밀도가 매우 높은 그래프를 표현할 때 효율적이다.
반면, 가장 큰 단점은 메모리 공간 효율성이 낮다는 것이다. V개의 정점을 가진 그래프를 표현하려면 V² 크기의 행렬이 필요하며, 희소 그래프의 경우 많은 공간이 낭비된다. 또한 특정 정점에 연결된 모든 이웃 정점을 찾는 연산은 O(V)의 시간이 소요되어 비효율적일 수 있다. 행렬 전체를 순회해야 하는 경우가 많기 때문이다.
인접 리스트의 가장 큰 장점은 메모리 사용이 효율적이라는 점이다. 실제 존재하는 간선만 저장하기 때문에, 희소 그래프에서 공간 복잡도는 O(V + E) 수준이다. 또한 특정 정점의 모든 인접 정점을 순회하는 작업이 해당 정점의 차수에 비례하는 시간만 소요되어 매우 효율적이다. 이는 너비 우선 탐색이나 깊이 우선 탐색과 같은 알고리즘에 유리하다.
주요 단점은 두 정점 사이의 특정 간선 존재 여부를 확인하는 데 O(V) 시간이 걸릴 수 있다는 것이다. 최악의 경우 해당 정점의 연결 리스트 전체를 탐색해야 한다. 또한 인접 행렬에 비해 구현이 다소 복잡할 수 있으며, 간선에 가중치를 저장하려면 추가적인 데이터 구조가 필요하다. 간선이 매우 많은 조밀한 그래프에서는 오히려 인접 행렬보다 더 많은 오버헤드가 발생할 수 있다.
인접 행렬 표현에서 특정 두 정점 사이에 간선이 존재하는지 확인하는 연산은 O(1)의 시간 복잡도를 가진다. 이는 행렬의 해당 인덱스를 직접 참조하기만 하면 되기 때문이다. 그러나 한 정점에 연결된 모든 이웃 정점을 찾는 연산은 O(V)의 시간이 소요된다. 여기서 V는 그래프의 총 정점 수를 의미한다. 행렬에서 해당 정점의 행 또는 열 전체를 순회해야 하기 때문이다. 마찬가지로, 그래프에 존재하는 모든 간선을 나열하는 작업은 O(V²)의 복잡도를 요구한다.
반면, 인접 리스트 표현에서는 한 정점의 모든 이웃을 탐색하는 데 걸리는 시간은 O(degree(V))이다. 여기서 degree(V)는 해당 정점의 차수, 즉 연결된 간선의 수를 의미한다. 이는 연결 리스트나 동적 배열을 순회하면 되므로 일반적으로 더 효율적이다. 그러나 두 정점 사이의 간선 존재 여부를 확인하려면 최악의 경우 해당 정점의 인접 리스트 전체를 검색해야 하므로 O(degree(V))의 시간이 걸린다. 모든 간선을 나열하는 작업은 모든 정점의 인접 리스트를 순회하면 되므로 O(V + E)의 시간이 소요된다. 여기서 E는 총 간선의 수이다.
다음 표는 주요 연산에 대한 두 표현법의 시간 복잡도를 비교하여 보여준다.
연산 | 인접 행렬 | 인접 리스트 |
|---|---|---|
두 정점 간 간선 존재 확인 | O(1) | O(degree(V)) |
정점의 모든 이웃 탐색 | O(V) | O(degree(V)) |
그래프의 모든 간선 나열 | O(V²) | O(V + E) |
새로운 간선 추가 | O(1) | O(1)[4] |
따라서, 간선 존재 확인이 빈번한 밀집 그래프에는 인접 행렬이 유리한 반면, 이웃 탐색이나 순회가 주를 이루는 희소 그래프에는 인접 리스트가 일반적으로 더 나은 시간 효율성을 보인다.
두 표현법의 메모리 사용량은 그래프의 밀도에 따라 크게 달라진다. 인접 행렬은 V개의 정점을 가진 그래프를 표현하기 위해 V×V 크기의 2차원 배열을 사용한다. 따라서 메모리 공간은 O(V²)에 비례한다. 이는 희소 그래프에서 많은 공간이 낭비될 수 있음을 의미한다. 반면, 인접 리스트는 각 정점에 연결된 간선의 리스트를 저장한다. 총 메모리 사용량은 정점의 수 V와 간선의 수 E에 비례하여 O(V + E)이다. 간선이 상대적으로 적은 희소 그래프에서는 인접 리스트가 훨씬 효율적인 메모리 사용을 보인다.
연산 효율성 측면에서도 두 방식은 상반된 특성을 가진다. 인접 행렬은 두 정점 사이에 특정 간선이 존재하는지 확인하는 연산을 O(1)의 상수 시간에 수행할 수 있다. 또한 정점 u에 인접한 모든 정점을 찾는 작업은 O(V) 시간이 걸린다. 인접 리스트에서는 간선 존재 여부를 확인하기 위해 리스트를 순회해야 하므로, 최악의 경우 O(V) 시간이 소요될 수 있다. 그러나 특정 정점에 인접한 모든 정점을 나열하는 작업은 해당 리스트의 길이, 즉 그 정점의 차수에 비례하는 시간(O(degree))이 걸려 일반적으로 더 효율적이다.
각 표현법은 서로 다른 그래프 유형에 더 적합하다. 인접 행렬은 간선이 매우 많은 밀집 그래프나 간선 존재 여부를 빈번히 확인해야 하는 알고리즘에 유리하다. 반면, 인접 리스트는 대부분의 실제 네트워크와 같은 희소 그래프를 표현하는 데 표준적으로 사용된다. 또한 그래프의 정점에 비해 간선의 수가 현저히 적은 경우, 메모리와 탐색 시간 모두에서 인접 리스트의 이점이 두드러진다.
비교 항목 | 인접 행렬 | 인접 리스트 |
|---|---|---|
메모리 공간 | O(V²) | O(V + E) |
간선 존재 확인 | O(1) | O(degree(v)) (최대 O(V)) |
정점의 이웃 탐색 | O(V) | O(degree(v)) |
새 간선 추가 | O(1) | O(1) (리스트 앞/뒤 추가 시) |
적합한 그래프 유형 | 밀집 그래프 | 희소 그래프 |
인접 행렬 표현법에서 필요한 메모리 공간은 정점의 수에 따라 제곱으로 증가합니다. V개의 정점을 가진 그래프를 표현하기 위해서는 일반적으로 V x V 크기의 2차원 배열이 필요합니다. 각 셀은 간선의 존재 유무나 가중치를 저장하므로, 전체 메모리 사용량은 O(V²)에 비례합니다. 이는 희소 그래프[5]의 경우 많은 공간이 낭비될 수 있습니다.
반면, 인접 리스트 표현법은 실제 존재하는 간선만을 저장합니다. 각 정점에 대해 연결된 이웃 정점들의 목록(리스트)을 유지합니다. 전체 메모리 사용량은 정점의 수 V와 간선의 수 E에 좌우됩니다. 방향 그래프의 경우 O(V + E), 무방향 그래프의 경우 O(V + 2E)의 공간을 차지합니다.
다음 표는 두 표현법의 메모리 사용 특성을 비교한 것입니다.
표현법 | 메모리 복잡도 (공간 복잡도) | 특징 |
|---|---|---|
인접 행렬 | O(V²) | 정점 수가 증가할수록 메모리 사용량이 급격히 증가함. 밀집 그래프[6]에 효율적. |
인접 리스트 | O(V + E) | 실제 간선 수에 비례하여 메모리를 사용함. 희소 그래프에서 공간 효율성이 매우 높음. |
따라서 간선의 수가 적은 희소 그래프에서는 인접 리스트가, 정점 수에 비해 간선이 매우 많은 밀집 그래프에서는 인접 행렬이 상대적으로 더 효율적인 메모리 사용을 보일 수 있습니다. 실제 선택은 그래프의 밀도와 수행할 주요 연산을 고려하여 결정됩니다.
인접 행렬 표현에서 특정 간선의 존재 여부를 확인하는 연산은 O(1)의 시간 복잡도를 가진다. 행렬의 (i, j) 위치를 직접 참조하여 값이 0인지 아닌지 확인하면 되기 때문이다. 반면, 인접 리스트에서는 정점 i의 연결 리스트를 순회하여 정점 j가 존재하는지 검사해야 하므로, 최악의 경우 O(V)의 시간이 소요될 수 있다[7].
정점에 연결된 모든 이웃 정점을 탐색하는 연산은 인접 리스트가 일반적으로 더 효율적이다. 인접 리스트는 해당 정점의 리스트 길이, 즉 차수만큼만 순회하면 되므로 O(deg(v))의 시간이 걸린다. 인접 행렬에서는 해당 정점에 대한 행 또는 열 전체를 스캔해야 하므로, 정점 수 V에 비례하는 O(V)의 시간이 필요하다.
간선을 추가하거나 삭제하는 연산에서도 차이가 나타난다. 인접 행렬은 행렬의 한 셀 값을 갱신하는 단순한 작업으로 O(1)에 처리할 수 있다. 인접 리스트의 경우, 간선 추가는 리스트의 맨 앞에 노드를 삽입하는 방식으로 O(1)에 가능하지만, 간선 삭제는 리스트에서 특정 노드를 찾아 제거해야 하므로 O(deg(v))의 시간이 소요된다.
연산 | 인접 행렬 | 인접 리스트 |
|---|---|---|
간선 존재 확인 | O(1) | O(deg(v)) (최대 O(V)) |
이웃 정점 순회 | O(V) | O(deg(v)) |
간선 추가 | O(1) | O(1) (보통 앞에 추가) |
간선 삭제 | O(1) | O(deg(v)) |
따라서, 간선 존재 여부를 자주 확인해야 하거나 밀집 그래프를 다루는 경우 인접 행렬이 유리하다. 반면, 그래프의 연결 구조를 탐색하거나 희소 그래프를 처리할 때는 인접 리스트가 더 효율적인 연산 성능을 보인다.
인접 행렬 표현은 정점의 수가 적고 간선이 밀집된 밀집 그래프에 적합하다. 모든 정점 쌍 간의 연결 관계를 상수 시간에 확인할 수 있어, 간선 존재 여부를 자주 검사해야 하는 알고리즘에 유리하다. 또한 구현이 직관적이고 간단하다는 장점이 있다.
반면, 인접 리스트 표현은 정점 수에 비해 간선 수가 상대적으로 적은 희소 그래프에 효율적이다. 실제 존재하는 간선만 저장하므로 메모리 사용량이 적다. 특정 정점에 연결된 모든 이웃 정점을 순회하는 연산이 빠르기 때문에, 깊이 우선 탐색이나 너비 우선 탐색과 같은 그래프 순회 알고리즘에서 주로 사용된다.
다음 표는 두 표현법의 주요 특성과 적합한 그래프 유형을 비교한 것이다.
특성 | 인접 행렬 | 인접 리스트 |
|---|---|---|
적합 그래프 유형 | ||
간선 존재 확인 | O(1) | O(degree(V))[8] |
이웃 정점 순회 | O(V) | O(degree(V)) |
메모리 공간 | O(V²) | O(V + E) |
따라서, 그래프의 밀도와 수행할 주요 연산의 종류에 따라 적절한 표현법을 선택해야 한다. 네트워크 토폴로지나 소셜 그래프와 같이 대부분 희소한 구조를 가진 현실 세계의 그래프에서는 인접 리스트가 더 일반적으로 사용된다.
깊이 우선 탐색(DFS)은 그래프의 모든 정점을 탐색하는 알고리즘이다. 스택 자료구조를 사용하거나 재귀 호출을 통해 구현한다. 알고리즘은 시작 정점을 방문하고, 그 정점에 인접한 아직 방문하지 않은 정점 중 하나를 선택해 깊이 들어가며 탐색한다. 더 이상 방문할 수 있는 정점이 없으면 이전 정점으로 돌아와 다른 경로를 탐색한다. 이 과정은 모든 정점을 방문할 때까지 반복된다. DFS는 인접 행렬로 구현할 경우 모든 정점에 대한 연결 여부를 확인해야 하므로 시간 복잡도가 O(V²)이다. 반면 인접 리스트로 구현하면 각 정점의 연결 리스트만 순회하면 되므로 O(V + E)의 시간 복잡도를 가진다.
너비 우선 탐색(BFS) 역시 그래프 탐색 알고리즘으로, 큐 자료구조를 사용한다. 시작 정점을 방문하고 큐에 넣은 후, 큐의 앞에서 정점을 꺼내 그 정점의 모든 인접 정점을 방문하며 큐에 추가한다. 이 과정을 큐가 빌 때까지 반복함으로써 시작 정점에서 가까운 정점들부터 차례대로 방문한다. BFS는 최단 경로 탐색에 유용하다. DFS와 마찬가지로 인접 행렬 표현에서는 O(V²), 인접 리스트 표현에서는 O(V + E)의 시간 복잡도를 가진다.
두 알고리즘의 구현은 그래프 표현 방식에 따라 달라진다. 인접 행렬을 사용할 때는 2차원 배열을 순회하며 연결 상태를 확인한다. 인접 리스트를 사용할 때는 각 정점에 연결된 리스트를 순회한다. 방문 여부를 추적하기 위해 별도의 배열(예: visited)을 사용하는 것은 공통적이다.
알고리즘 | 주요 자료구조 | 인접 행렬 시간 복잡도 | 인접 리스트 시간 복잡도 | 주요 특징 |
|---|---|---|---|---|
깊이 우선 탐색(DFS) | 스택(재귀 호출) | O(V²) | O(V + E) | 깊이 들어가는 경로 우선 탐색 |
너비 우선 탐색(BFS) | 큐 | O(V²) | O(V + E) | 시작점에서 가까운 정점 우선 탐색, 최단 경로 보장 |
깊이 우선 탐색(DFS)은 그래프나 트리의 모든 정점을 체계적으로 탐색하는 알고리즘이다. 이 방법은 현재 경로를 가능한 한 깊게 탐색한 후, 더 이상 진행할 수 없을 때 이전 정점으로 돌아와 다른 경로를 탐색하는 방식으로 작동한다. 일반적으로 재귀 호출이나 명시적인 스택 자료 구조를 사용하여 구현된다.
DFS의 기본 동작은 다음과 같다. 먼저 시작 정점을 방문하고 '방문 완료' 상태로 표시한다. 그런 다음 해당 정점에 인접한 아직 방문하지 않은 정점을 하나 선택하여 재귀적으로 동일한 과정을 반복한다. 인접한 모든 정점을 방문했다면, 이전 단계의 정점으로 돌아가(백트래킹) 남은 인접 정점에 대한 탐색을 계속한다. 이 과정은 그래프의 모든 정점을 방문할 때까지 반복된다.
DFS의 시간 복잡도는 그래프의 표현 방식에 따라 달라진다. 인접 행렬을 사용할 경우, 각 정점에서 다른 모든 정점을 확인해야 하므로 O(V²)의 시간이 소요된다(V는 정점의 수). 반면 인접 리스트를 사용하면 각 정점과 그에 연결된 간선만 탐색하므로 O(V + E)의 시간 복잡도를 가진다(E는 간선의 수). 공간 복잡도는 방문 상태를 저장하는 데 O(V), 재귀 호출 스택 또는 명시적 스택 사용으로 인해 최악의 경우 O(V)가 추가로 필요하다.
이 알고리즘은 위상 정렬, 연결 요소 찾기, 사이클 탐지, 미로 탐색 문제 등 다양한 응용 분야에서 활용된다. 또한 백트래킹을 이용한 퍼즐 해결이나 경로 탐색의 기반이 되기도 한다. 구현 시 그래프가 매우 깊거나 사이클이 존재할 경우 스택 오버플로가 발생할 수 있으므로 주의가 필요하다.
너비 우선 탐색(BFS)은 그래프나 트리의 모든 정점을 체계적으로 탐색하는 알고리즘이다. 시작 정점에서 가까운 정점들부터 차례대로 방문하는 방식으로, 같은 깊이(레벨)에 있는 모든 정점을 탐색한 후에 다음 깊이의 정점으로 넘어간다. 이 과정은 큐(Queue) 자료구조를 사용하여 구현된다.
BFS의 기본 동작 과정은 다음과 같다. 먼저 시작 정점을 큐에 넣고 방문했다고 표시한다. 큐가 빌 때까지, 큐의 앞에서 정점을 하나 꺼내고, 그 정점에 인접하면서 아직 방문하지 않은 모든 정점을 큐에 넣으며 방문 표시를 한다. 이 과정을 반복하면 시작점으로부터 거리가 가까운 순서대로 모든 정점을 방문하게 된다. 인접 행렬을 사용할 경우 모든 정점에 대한 연결 확인이 필요해 O(V²)의 시간이 걸릴 수 있지만, 인접 리스트를 사용하면 O(V + E)의 시간 복잡도로 효율적으로 수행된다.
BFS는 최단 경로 탐색에 유용하게 적용된다. 가중치가 없는 그래프에서 두 정점 사이의 최단 경로, 즉 가장 적은 수의 간선을 통한 경로를 찾을 수 있다. 또한 네트워크 브로드캐스팅, 페이스북이나 링크드인 같은 소셜 네트워크에서의 '친구 추천' 시스템, 웹 크롤링 등 다양한 분야에서 활용된다. 다음은 인접 리스트로 표현된 그래프에서 BFS를 수행하는 기본적인 의사코드 구조이다.
```
BFS(graph, start_vertex):
queue = new Queue()
visited = boolean array of size V, initialized to false
visited[start_vertex] = true
queue.enqueue(start_vertex)
while queue is not empty:
current = queue.dequeue()
process(current) // 현재 정점 처리 (예: 출력)
for each neighbor in graph.adjacency_list[current]:
if not visited[neighbor]:
visited[neighbor] = true
queue.enqueue(neighbor)
```
그래프 표현 방식은 다양한 실제 문제를 모델링하고 해결하는 데 널리 사용된다. 인접 행렬과 인접 리스트는 각각의 특성에 따라 다른 응용 분야에서 선호된다.
소셜 네트워크 분석에서는 인접 리스트가 효율적으로 활용된다. 페이스북이나 링크드인과 같은 플랫폼에서 사용자(정점)와 그들 사이의 친구 관계(간선)는 거대하면서도 희소 그래프의 특성을 보인다. 한 사용자가 수천 명의 친구를 가질 수 있지만, 전체 가능한 연결에 비해 실제 연결은 매우 적다. 이 경우 모든 가능한 연결을 저장하는 인접 행렬은 메모리 낭비가 심하지만, 인접 리스트는 실제 존재하는 연결만 저장하여 공간을 절약한다. "친구의 친구" 찾기나 특정 사용자의 연결망 분석과 같은 탐색 작업도 인접 리스트를 통해 해당 정점의 리스트만 순회하면 되므로 효율적이다.
경로 탐색 및 네트워크 라우팅 분야에서는 두 표현법이 상황에 따라 선택된다. 도로 네트워크나 인터넷 라우터 간 연결을 모델링할 때, 다익스트라 알고리즘이나 A* 알고리즘 같은 최단 경로 알고리즘은 종종 인접 리스트와 우선순위 큐를 조합하여 사용한다. 이는 알고리즘이 특정 정점에 연결된 모든 간선(인접 리스트)을 빠르게 열거해야 하기 때문이다. 반면, 플로이드-워셜 알고리즘처럼 모든 정점 쌍 간의 최단 거리를 계산해야 하는 경우에는 전체 연결 상태에 대한 빠른 접근이 필요하여 인접 행렬이 더 적합할 수 있다. 네트워크 대역폭이나 거리 같은 가중치 정보는 두 표현법 모두에서 간선 데이터의 일부로 저장된다.
응용 분야 | 주로 사용하는 표현법 | 주요 이유 |
|---|---|---|
소셜 네트워크 (친구 관계) | 그래프가 희소 그래프이며, 특정 노드의 이웃 탐색이 빈번함 | |
도로 네트워크 (내비게이션) | 교차로마다 나가는 도로 수가 제한적이며, 경로 탐색 알고리즘에 적합함 | |
모든 쌍 최단 경로 계산 | 임의의 두 정점 간 연결 존재 여부를 상수 시간에 확인할 수 있음 | |
작고 밀집된 그래프 시뮬레이션 | 정점 수가 적고 간선이 많아 행렬이 공간 낭비가 적으며, 간선 추가/삭제가 쉬움 |
이 외에도 인접 행렬은 그래프의 연결성을 행렬 연산을 통해 분석하는 데 유용하다. 예를 들어, 인접 행렬을 거듭제곱하면 정점 간 길이 *k*인 경로의 수를 계산할 수 있다[9]. 인접 리스트는 의존성 그래프에서의 위상 정렬이나 컴파일러의 제어 흐름 그래프 분석과 같이 동적인 탐색이 중요한 알고리즘 구현에 필수적이다.
소셜 네트워크 분석은 그래프 이론을 활용하여 사회적 관계를 구조적으로 연구하는 분야이다. 이 분석에서 개인 또는 조직은 정점으로, 그들 사이의 관계(예: 친구 관계, 팔로우, 협업)는 간선으로 모델링된다. 이러한 네트워크는 일반적으로 방향성이 있을 수도 있고 없을 수도 있으며, 간선에 관계의 강도나 빈도와 같은 가중치를 부여할 수 있다. 소셜 네트워크 분석의 주요 목표는 네트워크의 전반적 구조를 이해하고, 영향력 있는 노드(예: 중심성)를 식별하며, 정보나 행동의 확산 경로를 예측하는 것이다.
인접 행렬과 인접 리스트는 소셜 네트워크를 표현하는 데 각각 장단점을 가진다. 대규모 소셜 네트워크(예: 수백만 명의 사용자를 가진 SNS)는 일반적으로 희소 그래프의 특성을 보이므로, 인접 리스트 표현이 메모리 효율성 면에서 더 유리하다. 특정 두 사용자 간의 직접적인 연결 존재 여부를 빠르게 확인해야 하는 분석에는 인접 행렬이 O(1) 시간 복잡도로 유리할 수 있지만, 한 사용자의 모든 친구(이웃 정점)를 나열하는 작업은 인접 리스트에서 더 효율적이다.
분석 작업에 따라 적합한 표현법이 달라진다. 네트워크의 군집 구조를 분석하거나 너비 우선 탐색을 통한 확산 시뮬레이션을 실행할 때는 인접 리스트가 일반적으로 선호된다. 반면, 네트워크 전체의 연결성을 한눈에 살펴보거나 행렬 연산을 기반으로 하는 고급 분석(예: 페이지랭크 알고리즘의 일부 계산)을 수행할 때는 인접 행렬이 유용할 수 있다. 실제 소셜 네트워크 분석 도구와 라이브러리들은 대용량 데이터를 효율적으로 처리하기 위해 인접 리스트 또는 그 변형 구조를 주로 사용한다.
경로 탐색은 출발 정점에서 목표 정점까지의 경로를 찾는 문제이다. 네트워크 라우팅은 네트워크 상에서 데이터 패킷이 최적의 경로를 통해 목적지에 도달하도록 하는 과정을 의미한다. 이 두 분야는 그래프 이론을 기반으로 하며, 인접 행렬과 인접 리스트와 같은 그래프 표현 방식은 사용되는 알고리즘의 효율성에 직접적인 영향을 미친다.
대표적인 경로 탐색 알고리즘으로는 다익스트라 알고리즘과 A* 알고리즘이 있다. 다익스트라 알고리즘은 가중치가 있는 그래프에서 한 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는다. 이 알고리즘은 우선순위 큐와 함께 사용될 때, 인접 리스트 표현을 사용하면 O(|V| + |E| log |V|)의 시간 복잡도를 가진다[10]. 반면, 인접 행렬을 사용하면 모든 정점 쌍을 확인해야 할 수 있어 일반적으로 더 비효율적이다. A* 알고리즘은 휴리스틱을 사용하여 목표 지향적인 탐색을 수행하며, 게임의 길 찾기나 지리 정보 시스템(GIS)에서 널리 사용된다.
네트워크 라우팅에서는 링크 상태 라우팅 프로토콜과 거리 벡터 라우팅 프로토콜이 대표적이다. 링크 상태 라우팅(예: OSPF)은 네트워크의 모든 라우터가 전체 네트워크 토폴로지에 대한 정보를 유지한다. 이는 각 라우터가 네트워크를 하나의 완전한 그래프로 인식하고, 일반적으로 인접 리스트와 유사한 방식으로 이웃 연결 상태를 관리함을 의미한다. 반면, 거리 벡터 라우팅(예: RIP)은 각 라우터가 이웃에게만 자신의 라우팅 테이블을 광고하는 방식으로, 전체 경로 정보보다는 목적지까지의 거리와 방향(벡터) 정보를 저장한다.
알고리즘/프로토콜 | 주요 사용 그래프 표현 | 핵심 특징 |
|---|---|---|
주로 인접 리스트 | 단일 출발점 최단 경로, 가중치 적용 | |
주로 인접 리스트 | 휴리스틱을 이용한 목표 지향 탐색 | |
OSPF (링크 상태) | 인접 리스트 개념 | 전체 네트워크 맵 유지, 빠른 수렴 |
RIP (거리 벡터) | 간소화된 테이블 | 이웃과만 정보 교환, 간단한 구현 |
이러한 응용 분야에서 인접 리스트는 그래프가 희소 그래프인 경우, 즉 간선의 수가 정점 수의 제곱에 비해 훨씬 적은 경우 메모리 효율성과 탐색 속도 면에서 유리하다. 인접 행렬은 밀집 그래프이거나 특정 정점 쌍의 연결 존재 여부를 상수 시간(O(1)) 내에 확인해야 하는 경우에 더 적합할 수 있다.
