그래프는 컴퓨터 과학과 알고리즘 분야에서 가장 기본적이면서도 핵심적인 자료구조 중 하나다. 정점(Vertex)과 간선(Edge)이라는 두 개념만으로 구성되지만, 이를 통해 모델링할 수 있는 세계는 놀랍도록 다양하다. 도시 간 도로망, 소셜 네트워크, 웹페이지 링크 구조, 네트워크 인프라 등 실세계의 수많은 문제들이 그래프 형태로 표현될 수 있다.
그래프를 다루는 알고리즘을 이해하려면, 그래프가 무엇인지뿐 아니라 그 위에서 수행하는 연산들이 어떤 시간 복잡도를 가지는지 정확히 파악해야 한다. 특히 그래프 탐색 알고리즘에서 흔히 등장하는 시간 복잡도 표현인 O(V+E)는 매우 중요한 개념이다.
그래프의 기본 구성 요소
**정점(Vertex)**은 개별 객체를 나타낸다. 예를 들어, 하나의 도시, 하나의 사람, 하나의 컴퓨터 등이 정점이 될 수 있다.
**간선(Edge)**은 정점과 정점 간의 관계나 연결을 나타낸다. 도시 간 도로, 사람 간 친구 관계, 컴퓨터 간 네트워크 링크 등이 이에 해당한다.
그래프의 표현 방법
그래프를 컴퓨터 내에 저장하는 방법에는 크게 두 가지가 있다.
- 인접 행렬(Adjacency Matrix): 정점 수 V에 대해 V×V 크기의 2차원 배열을 사용해 정점 간 연결 여부를 나타낸다. 메모리 사용량이 O(V²)로 많지만, 두 정점 사이의 연결 여부를 빠르게 확인할 수 있다.
- 인접 리스트(Adjacency List): 각 정점마다 연결된 정점 리스트를 따로 관리한다. 메모리 사용량이 O(V+E)로 효율적이며, 많은 경우 현실의 희소 그래프(Sparse Graph)를 다룰 때 인접 리스트를 사용한다.
대부분의 그래프 탐색 알고리즘에서는 인접 리스트가 사용된다. 이는 O(V+E) 시간 복잡도를 가능하게 만드는 핵심 요소다.
시간 복잡도 O(V+E)란 무엇인가
그래프 탐색 알고리즘에서 “O(V+E)”라는 시간 복잡도가 등장하는 이유는 탐색 과정이 정점과 간선 각각을 한 번씩만 처리하기 때문이다.
- O(V): 모든 정점을 방문하는 데 걸리는 시간이다. 그래프의 모든 정점을 한 번씩 체크하거나 초기화하거나 탐색해야 할 수 있다.
- O(E): 모든 간선을 따라가는 데 걸리는 시간이다. 각 정점에 연결된 간선을 모두 검사해야 하기 때문이다.
즉, 그래프 탐색은 “정점 수 + 간선 수”만큼의 시간이 필요하므로, 총 복잡도는 **O(V+E)**가 된다.
O(V+E) 시간 복잡도를 가지는 대표 알고리즘
- BFS (Breadth-First Search, 너비 우선 탐색)
- 인접 정점을 순차적으로 탐색한다.
- 큐(Queue)를 이용해 가장 가까운 정점부터 차례로 방문한다.
- DFS (Depth-First Search, 깊이 우선 탐색)
- 한 방향으로 깊이 파고들다가 막히면 다시 돌아가며 탐색한다.
- 스택(Stack)이나 재귀 호출을 사용한다.
- 위상 정렬 (Topological Sort)
- 방향성이 있고 사이클이 없는 그래프(DAG)에서 정점들을 순서대로 나열한다.
- 선후 관계가 중요한 작업 스케줄링 등에 쓰인다.
- SCC (Strongly Connected Components, 강한 연결 요소 찾기)
- 방향 그래프에서 모든 정점 간에 경로가 존재하는 집합을 찾는다.
- 타잔(Tarjan) 알고리즘, 코사라주(Kosaraju) 알고리즘 등이 대표적이다.
이들 알고리즘은 모두 인접 리스트를 기반으로 할 때 O(V+E)의 시간 안에 문제를 해결할 수 있다.
인접 리스트와 인접 행렬의 시간 복잡도 차이
만약 인접 행렬을 사용한다면, 모든 정점 쌍을 확인해야 하므로 O(V²) 시간이 소요된다. 이는 정점 수가 많을 때 비효율적이다. 반면 인접 리스트를 사용하면 실제로 존재하는 간선만 검사하면 되므로 O(E) 시간만 소요된다.
실제로, 대부분의 현실 세계 그래프는 희소 그래프(Sparse Graph), 즉 간선 수 E가 정점 수 V에 비해 매우 적기 때문에 인접 리스트 기반 탐색이 훨씬 효율적이다.
O(V+E) 복잡도의 의미를 다시 강조하면
- V: 탐색하는 데 필요한 “정점 수”
- E: 탐색하는 데 필요한 “간선 수”
- 그래프 탐색은 “정점과 간선 모두 한 번씩만 건드리는 작업”이기 때문에 두 항을 더한 O(V+E)가 되는 것이다.
결론
그래프 알고리즘을 공부할 때 단순히 코드를 외우는 것보다, 왜 시간 복잡도가 O(V+E)인지, 인접 리스트를 쓰는 이유는 무엇인지를 이해하는 것이 훨씬 중요하다.
이러한 이해를 바탕으로 다양한 그래프 문제를 접할 때마다 적절한 자료구조와 알고리즘을 선택할 수 있다.
그래프 이론은 분명 복잡하지만, 본질을 꿰뚫어 보면 세상을 모델링하고 문제를 해결하는 데 막강한 도구가 된다.
답글 남기기