JeroCaller

쌓여만 가는 빈 캔

4 분 소요

Adjacency matrix (인접 행렬)

인접 행렬은 그래프의 노드들 간의 연결관계를 2차원의 N * N 크기의 행렬과 그만큼의 boolean 값들을 담아 표현한다. 해당 행렬을 M으로 표기하면, 행에 담긴 노드 u와 열에 담긴 노드 v에 대해 M[u][v]로 접근하면 해당 값은 노드 u와 v가 엣지로 연결되어있는지 여부(즉, 엣지 존재 여부)를 boolean값으로 저장한다. u = v라면 해당 값은 False로 해둔다.

그림1. weighted-directed graph 예.

그림1. weighted-directed graph 예.

그림2. 그림 1을 토대로 노드들간 연결관계를 인접행렬로 표현한 모습.

그림2. 그림 1을 토대로 노드들간 연결관계를 인접행렬로 표현한 모습.

그래프 탐색을 위해 인접 행렬이 쓰인다면, 해당 그래프 탐색 알고리즘의 인접 행렬에 의한 복잡도는 어떻게 계산될까?

특정 노드 u의 인접한 노드들을 검색하기 위해선 해당 노드의 실제 인접 노드들의 개수에 상관없이 모든 노드들을 검색해야만 해당 노드에 인접한 노드들이 무엇이고 몇 개인지를 파악할 수 있다. 즉, N개의 노드들을 검색해야 한다. 따라서 이 경우(즉, 모든 인접 노드 확인 작업의 경우) 시간복잡도는 O(N)이다. 그런데 앞서 미로 문제에서 DFS, BFS, greedy BFS 알고리즘들의 코드를 보면 알겠지만, 최악의 경우, 존재하는 모든 노드들을 탐색해봐야한다. 이는 보통 while문을 통해 이루어졌고, 알고리즘 구현에 사용되었던 스택, 큐, 우선순위 큐 자료구조 내에 노드 정보가 모두 사라질 때까지 진행되었다. 즉, 탐색 자체도 최악의 경우 O(N)의 시간복잡도를 가진다. 따라서, 노드 한 번을 탐색할 때마다 그와 동시에 그 노드의 인접 노드들도 조사해야하는 구조이기에 인접 행렬 사용 시 시간복잡도는 최악의 경우 \(O(N^2)\)이다. (여기서의 시간복잡도는 특정 노드의 전체 인접 노드 파악 횟수와 그래프 탐색 횟수만을 고려한 것이다. 알고리즘 내에 사용된 자료구조에 데이터 삽입, 삭제의 요소는 고려하지 않은 것이다)

공간복잡도도 마찬가지로, N^2만큼의 boolean 정보가 필요한 셈이므로 역시 \(O(N^2)\)라고 할 수 있다.

Adjacency list (인접 리스트)

앞서 미로 찾기 문제에서, 찾은 경로를 재구성하기 위해 딕셔너리 안에 현재 노드와 그 현재 노드로 접근할 수 있는 바로 이전 노드를 각각 key-value 쌍 데이터로 저장하였다. 실제로 인접 리스트는 각각의 노드 u를 key로 하고, 그 노드에 인접한 (즉, 노드 u로 향하도록 직접 연결된 인접 노드들) 노드들을 연결리스트로 연결하여 value로 하는 해시테이블을 기반으로 사용한다.

그림 1을 인접 리스트로 표현하면 다음과 같겠다.

a: b
b: a -> c -> d
c: a -> d
d: b

DFS 문서에서 DFS를 구현했던 코드 일부분을 다시 살펴보자.

while not stack.is_empty():
    node = stack.pop()
    for adjacent_node in self.G[node]:
        if adjacent_node not in visited:
            cp_nodes[adjacent_node] = node
            visited[adjacent_node] = True
            stack.push(adjacent_node)

스택, 큐 등의 자료구조에 특정 노드 u가 삽입되는 횟수는 단 한 번뿐이다. 그리고 예제 1-1을 보면, 인접 노드들 중 방문한 노드들이 있는지 확인하는 if문이 있는데, 이렇게 방문한 노드들이 있는지 확인하려면 우선 모든 인접 노드들을 방문해야만 한다. 다시 말하면, 인접 노드들과 연결된 모든 edge들을 방문해야 하는 것이다. 그래프의 인접한 노드들의 관계를 인접 리스트로 구성해놓은 경우, 그래프 내 모든 edge들을 방문해야 하는 최악의 경우에는 무방향 그래프의 경우에는 총 2 * E만큼의 접근이 필요하다. 그래프에 두 노드 u, v만이 존재하고 둘이 간선으로 연결되어 있다고 할 때, 처음에는 u를 중점으로 인접 노드를 검사한다. 이는 인접 노드가 이미 방문되었는지 아닌지 상관없이 이루어진다. 따라서 v에 반드시 접근할 수 밖에 없다. 반대로 v의 차례가 왔을 때도, 인접 노드인 u에 접근할 수밖에 없다. 방문했는지 아닌지 상관없이 말이다. 즉, 두 노드가 있을 때 총 2번 동안 edge를 방문했기에 이를 확장하면 2 * E가 되는 것이다. (유방향 그래프의 경우, 일방통행의 edge들도 존재해서, 모든 edge가 일방통행일 경우 E가 되겠다)

최악의 경우, 그래프의 모든 노드들을 탐색해야 한다. 즉 N개의 노드들을 탐색해야 한다. 따라서 인접 리스트의 경우, 최악의 경우 시간복잡도는 \(O(N+E)\)가 되겠다. 여기서 N은 그래프 내 모든 노드들의 수, E는 그래프 내 모든 edge들의 수를 의미한다. (여기서의 시간복잡도도 마찬가지로, 특정 노드 내 인접 노드를 파악하는 횟수와 그래프 탐색 횟수만을 고려한 것이지, 자료구조에 따른 데이터 삽입, 삭제에 의한 복잡도는 고려하지 않았다)

공간복잡도도 마찬가지로, 그래프 내 모든 노드의 수 + 모든 엣지의 수이므로 역시나 최악의 경우 \(O(N+E)\)라 할 수 있겠다.

정리

  • 인접 행렬을 사용하여 그래프 탐색 시의 최악의 복잡도: \(O(N^2)\)
  • 인접 리스트를 사용하여 그래프 탐색 시의 최악의 복잡도: \(O(N+E)\)

그래프에서 Edge의 수가 최대일 경우는 각각의 노드가 나머지 모든 노드들과 연결되어 있을 때이다(즉 완전그래프일 경우). 이 경우 Edge의 개수는 \(\frac{N(N-1)}{2}\)이다. 이럴 경우, 인접 리스트의 최악의 복잡도도 \(O(N^2)\)이다. 하지만 일반적으로는 모든 노드가 다른 모든 노드들과 연결되어 있다는 보장이 없기에 (즉, edge의 개수가 그때그때 다르므로) 보통 E로 표시한다.

인접 리스트에서 특정 노드 u에 v가 인접해있는지 확인하는 작업은 O(degree(u))의 시간복잡도를 가진다. 여기서 degree는 특정 노드에 연결된 edge의 수이다. 인접 리스트는 각각의 노드들에 대해 인접한 노드들의 정보가 연결 리스트로 구성되어 있기에, 최악의 경우 하나의 연결 리스트를 모두 순회해야하기 때문이다.

DFS, BFS, greedy BFS의 복잡도

그래프 탐색 알고리즘의 복잡도를 파악하기 위해선 앞서 살펴본 인접 행렬을 사용했느냐 인접 리스트를 사용했냐를 고려하는 것도 있지만, 각각의 알고리즘이 어떤 자료구조를 사용했느냐도 고려해봐야 한다.

DFS의 경우, 스택을 사용하였다. 스택에 데이터를 삽입하고 꺼내는 시간복잡도 모두 O(1)이다. 따라서 DFS의 시간복잡도는 오로지 인접 행렬을 사용하느냐 인접 리스트를 사용하느냐에 따라 달리게 된다.

이는 BFS도 마찬가지이다. 큐의 데이터 삽입도 삭제도 모두 시간복잡도가 O(1)이다. 역시나 인접 리스트를 사용했느냐 인접 행렬을 사용했느냐에 시간복잡도 계산이 달려있게 된다.

그래서 사실 앞서 설명한 인접 행렬 또는 인접 리스트를 사용했을 때의 그래프 탐색 시의 시간복잡도는 DFS, BFS의 시간복잡도와 같다.

greedy BFS는 앞서 A* 알고리즘 & Greedy Best-First Search 문서에서 언급했듯, 최악의 경우 시간복잡도가 $O(b^m)$이었다. 다만, 해당 문서에서 4방향으로만 이동할 수 있는 미로 문제에 대해 다뤘는데, 이 문제에 한하면 얘기는 조금 달라진다. 무선 휴리스틱 함수로 사용되었던 맨하탄 거리 계산 메서드는 그 자체로는 그래프에 포함된 노드, 간선의 개수에 상관없이 두 노드만을 대상으로 하여 두 노드 간의 좌표 차이를 구하는 방식이었다. 따라서 해당 메서드 자체는 시간복잡도가 O(1)이라고 할 수 있겠다. 그 다음 고려사항은 해당 알고리즘에 사용된 자료구조의 복잡도를 따지는 것인데, 해당 문제에서는 우선순위 큐가 사용되었다. 우선순위 큐는 데이터의 삽입과 삭제 모두 그 시간복잡도가 \(O(\log N)\)이었다. 최악의 경우, 이러한 우선순위 큐의 삽입과 삭제 횟수가 N번동안 진행되므로, 해당 알고리즘이 인접 리스트를 사용 시 \(O(N \log N)\)이라 할 수 있겠다. 여기에, 인접 리스트의 경우 간선의 개수 E도 고려해야하기에 최종적으로 해당 알고리즘의 최악의 경우의 시간복잡도는 \(O(N \log N + E)\)라고 할 수 있겠다. (공간복잡도는 인접리스트의 경우 \(O(N +E)\)이었고, 우선순위 큐에는 최대 N개의 데이터가 저장되므로 총 \(O(N+E)\)이라고 할 수 있겠다) 인접 행렬을 사용하는 경우, \(N\log N < N^2\)이기에 최악의 경우의 시간복잡도는 \(O(N^2)\)이라고 할 수 있겠다.

Reference

[1] George T. Heineman, “Learning Algorithms: A Programmer’s Guide to Writing Better Code”, (O’Reilly, 2021)

This content is licensed under CC BY-NC 4.0

댓글남기기

참고