그래프(인접 행렬 및 리스트)편집자 확인

그래프는 정점과 간선의 집합으로 구성된 자료 구조이다. 정점은 그래프의 기본 구성 요소로, 객체나 개체를 나타낸다. 간선은 두 정점 사이의 연결 관계를 표현한다.

정점은 보통 V로 표시되며, 각 정점은 고유한 식별자(예: 번호나 이름)로 구분된다. 간선은 보통 E로 표시되며, 두 정점의 쌍 (u, v)으로 정의된다. 간선의 종류에 따라 그래프는 무방향 그래프와 방향 그래프로 나뉜다. 무방향 그래프에서 간선 (u, v)는 정점 u와 v가 서로 연결되어 있음을 의미하며, 방향 그래프에서 간선 (u, v)는 u에서 v로의 단방향 연결을 의미한다.

정점과 간선의 개념은 네트워크, 지도, 소셜 미디어 관계 등 다양한 현실 세계의 문제를 추상화하는 데 사용된다. 예를 들어, 소셜 네트워크에서 사람은 정점이 되고, 친구 관계는 간선이 된다.

그래프는 간선에 방향성이 존재하는지 여부에 따라 방향 그래프와 무방향 그래프로 구분된다. 방향 그래프에서는 간선이 한 정점에서 다른 정점으로의 방향을 가지며, (u, v)와 (v, u)는 서로 다른 간선으로 취급된다. 반면 무방향 그래프에서는 간선이 양방향 연결을 의미하며, (u, v)와 (v, u)는 동일한 간선이다.

간선에 추가적인 수치 정보가 부여된 그래프를 가중 그래프라고 한다. 이때 부여된 값을 가중치라고 하며, 이는 거리, 비용, 시간, 용량 등 다양한 의미를 가질 수 있다. 가중치가 없는 그래프는 비가중 그래프로, 모든 간선의 가중치가 동일한 것으로 간주된다.

방향성과 가중치의 조합에 따라 그래프는 네 가지 주요 유형으로 분류될 수 있다.

이러한 특성은 그래프를 표현하는 인접 행렬이나 인접 리스트의 구조와 사용되는 알고리즘의 선택에 직접적인 영향을 미친다. 예를 들어, 방향 그래프의 인접 행렬은 대칭적이지 않을 수 있으며, 가중 그래프의 경우 행렬 셀이나 리스트 노드에 가중치 값을 저장해야 한다.

인접 행렬은 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)) 시간이 걸린다.

따라서, 간선 검색이 빈번한 응용에는 인접 행렬이, 그래프 순회나 이웃 탐색이 주를 이루는 알고리즘에는 인접 리스트가 일반적으로 더 유리한 시간적 특성을 보인다.

인접 행렬은 2차원 배열을 사용하여 그래프의 연결 관계를 표현하는 방법이다. 행과 열 모두 정점에 대응되며, 행렬의 각 요소는 두 정점 사이의 간선 존재 여부 또는 가중치를 나타낸다.

무방향 그래프의 경우, 행렬은 주대각선을 기준으로 대칭 구조를 가진다. 정점 i와 정점 j 사이에 간선이 존재하면, matrix[i][j]와 matrix[j][i]의 값을 1(또는 가중치)로 설정한다. 가중치가 없는 그래프에서는 일반적으로 간선이 있으면 1, 없으면 0으로 표시한다. 가중 그래프의 경우, 해당 위치에 가중치 값을 저장하고, 간선이 없음을 나타내는 값(예: 0, 무한대, 또는 -1)을 사용한다.

위 표는 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는 총 간선의 수이다.

다음 표는 주요 연산에 대한 두 표현법의 시간 복잡도를 비교하여 보여준다.

따라서, 간선 존재 확인이 빈번한 밀집 그래프에는 인접 행렬이 유리한 반면, 이웃 탐색이나 순회가 주를 이루는 희소 그래프에는 인접 리스트가 일반적으로 더 나은 시간 효율성을 보인다.

인접 행렬 표현법에서 필요한 메모리 공간은 정점의 수에 따라 제곱으로 증가합니다. V개의 정점을 가진 그래프를 표현하기 위해서는 일반적으로 V x V 크기의 2차원 배열이 필요합니다. 각 셀은 간선의 존재 유무나 가중치를 저장하므로, 전체 메모리 사용량은 O(V²)에 비례합니다. 이는 희소 그래프[5]의 경우 많은 공간이 낭비될 수 있습니다.

반면, 인접 리스트 표현법은 실제 존재하는 간선만을 저장합니다. 각 정점에 대해 연결된 이웃 정점들의 목록(리스트)을 유지합니다. 전체 메모리 사용량은 정점의 수 V와 간선의 수 E에 좌우됩니다. 방향 그래프의 경우 O(V + E), 무방향 그래프의 경우 O(V + 2E)의 공간을 차지합니다.

다음 표는 두 표현법의 메모리 사용 특성을 비교한 것입니다.

따라서 간선의 수가 적은 희소 그래프에서는 인접 리스트가, 정점 수에 비해 간선이 매우 많은 밀집 그래프에서는 인접 행렬이 상대적으로 더 효율적인 메모리 사용을 보일 수 있습니다. 실제 선택은 그래프의 밀도와 수행할 주요 연산을 고려하여 결정됩니다.

인접 행렬 표현에서 특정 간선의 존재 여부를 확인하는 연산은 O(1)의 시간 복잡도를 가진다. 행렬의 (i, j) 위치를 직접 참조하여 값이 0인지 아닌지 확인하면 되기 때문이다. 반면, 인접 리스트에서는 정점 i의 연결 리스트를 순회하여 정점 j가 존재하는지 검사해야 하므로, 최악의 경우 O(V)의 시간이 소요될 수 있다[7].

정점에 연결된 모든 이웃 정점을 탐색하는 연산은 인접 리스트가 일반적으로 더 효율적이다. 인접 리스트는 해당 정점의 리스트 길이, 즉 차수만큼만 순회하면 되므로 O(deg(v))의 시간이 걸린다. 인접 행렬에서는 해당 정점에 대한 행 또는 열 전체를 스캔해야 하므로, 정점 수 V에 비례하는 O(V)의 시간이 필요하다.

간선을 추가하거나 삭제하는 연산에서도 차이가 나타난다. 인접 행렬은 행렬의 한 셀 값을 갱신하는 단순한 작업으로 O(1)에 처리할 수 있다. 인접 리스트의 경우, 간선 추가는 리스트의 맨 앞에 노드를 삽입하는 방식으로 O(1)에 가능하지만, 간선 삭제는 리스트에서 특정 노드를 찾아 제거해야 하므로 O(deg(v))의 시간이 소요된다.

따라서, 간선 존재 여부를 자주 확인해야 하거나 밀집 그래프를 다루는 경우 인접 행렬이 유리하다. 반면, 그래프의 연결 구조를 탐색하거나 희소 그래프를 처리할 때는 인접 리스트가 더 효율적인 연산 성능을 보인다.

인접 행렬 표현은 정점의 수가 적고 간선이 밀집된 밀집 그래프에 적합하다. 모든 정점 쌍 간의 연결 관계를 상수 시간에 확인할 수 있어, 간선 존재 여부를 자주 검사해야 하는 알고리즘에 유리하다. 또한 구현이 직관적이고 간단하다는 장점이 있다.

반면, 인접 리스트 표현은 정점 수에 비해 간선 수가 상대적으로 적은 희소 그래프에 효율적이다. 실제 존재하는 간선만 저장하므로 메모리 사용량이 적다. 특정 정점에 연결된 모든 이웃 정점을 순회하는 연산이 빠르기 때문에, 깊이 우선 탐색이나 너비 우선 탐색과 같은 그래프 순회 알고리즘에서 주로 사용된다.

다음 표는 두 표현법의 주요 특성과 적합한 그래프 유형을 비교한 것이다.

따라서, 그래프의 밀도와 수행할 주요 연산의 종류에 따라 적절한 표현법을 선택해야 한다. 네트워크 토폴로지나 소셜 그래프와 같이 대부분 희소한 구조를 가진 현실 세계의 그래프에서는 인접 리스트가 더 일반적으로 사용된다.

깊이 우선 탐색(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)

```

소셜 네트워크 분석은 그래프 이론을 활용하여 사회적 관계를 구조적으로 연구하는 분야이다. 이 분석에서 개인 또는 조직은 정점으로, 그들 사이의 관계(예: 친구 관계, 팔로우, 협업)는 간선으로 모델링된다. 이러한 네트워크는 일반적으로 방향성이 있을 수도 있고 없을 수도 있으며, 간선에 관계의 강도나 빈도와 같은 가중치를 부여할 수 있다. 소셜 네트워크 분석의 주요 목표는 네트워크의 전반적 구조를 이해하고, 영향력 있는 노드(예: 중심성)를 식별하며, 정보나 행동의 확산 경로를 예측하는 것이다.

인접 행렬과 인접 리스트는 소셜 네트워크를 표현하는 데 각각 장단점을 가진다. 대규모 소셜 네트워크(예: 수백만 명의 사용자를 가진 SNS)는 일반적으로 희소 그래프의 특성을 보이므로, 인접 리스트 표현이 메모리 효율성 면에서 더 유리하다. 특정 두 사용자 간의 직접적인 연결 존재 여부를 빠르게 확인해야 하는 분석에는 인접 행렬이 O(1) 시간 복잡도로 유리할 수 있지만, 한 사용자의 모든 친구(이웃 정점)를 나열하는 작업은 인접 리스트에서 더 효율적이다.

분석 작업에 따라 적합한 표현법이 달라진다. 네트워크의 군집 구조를 분석하거나 너비 우선 탐색을 통한 확산 시뮬레이션을 실행할 때는 인접 리스트가 일반적으로 선호된다. 반면, 네트워크 전체의 연결성을 한눈에 살펴보거나 행렬 연산을 기반으로 하는 고급 분석(예: 페이지랭크 알고리즘의 일부 계산)을 수행할 때는 인접 행렬이 유용할 수 있다. 실제 소셜 네트워크 분석 도구와 라이브러리들은 대용량 데이터를 효율적으로 처리하기 위해 인접 리스트 또는 그 변형 구조를 주로 사용한다.

경로 탐색은 출발 정점에서 목표 정점까지의 경로를 찾는 문제이다. 네트워크 라우팅은 네트워크 상에서 데이터 패킷이 최적의 경로를 통해 목적지에 도달하도록 하는 과정을 의미한다. 이 두 분야는 그래프 이론을 기반으로 하며, 인접 행렬과 인접 리스트와 같은 그래프 표현 방식은 사용되는 알고리즘의 효율성에 직접적인 영향을 미친다.

대표적인 경로 탐색 알고리즘으로는 다익스트라 알고리즘과 A* 알고리즘이 있다. 다익스트라 알고리즘은 가중치가 있는 그래프에서 한 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는다. 이 알고리즘은 우선순위 큐와 함께 사용될 때, 인접 리스트 표현을 사용하면 O(|V| + |E| log |V|)의 시간 복잡도를 가진다[10]. 반면, 인접 행렬을 사용하면 모든 정점 쌍을 확인해야 할 수 있어 일반적으로 더 비효율적이다. A* 알고리즘은 휴리스틱을 사용하여 목표 지향적인 탐색을 수행하며, 게임의 길 찾기나 지리 정보 시스템(GIS)에서 널리 사용된다.

네트워크 라우팅에서는 링크 상태 라우팅 프로토콜과 거리 벡터 라우팅 프로토콜이 대표적이다. 링크 상태 라우팅(예: OSPF)은 네트워크의 모든 라우터가 전체 네트워크 토폴로지에 대한 정보를 유지한다. 이는 각 라우터가 네트워크를 하나의 완전한 그래프로 인식하고, 일반적으로 인접 리스트와 유사한 방식으로 이웃 연결 상태를 관리함을 의미한다. 반면, 거리 벡터 라우팅(예: RIP)은 각 라우터가 이웃에게만 자신의 라우팅 테이블을 광고하는 방식으로, 전체 경로 정보보다는 목적지까지의 거리와 방향(벡터) 정보를 저장한다.

이러한 응용 분야에서 인접 리스트는 그래프가 희소 그래프인 경우, 즉 간선의 수가 정점 수의 제곱에 비해 훨씬 적은 경우 메모리 효율성과 탐색 속도 면에서 유리하다. 인접 행렬은 밀집 그래프이거나 특정 정점 쌍의 연결 존재 여부를 상수 시간(O(1)) 내에 확인해야 하는 경우에 더 적합할 수 있다.