그래프(Graph) 기초: 지하철 노선도로 배우는 점과 선의 연결
배열이나 스택, 큐처럼 데이터가 일렬로 나열되는 '선형(Linear)' 자료구조만으로는 현실 세계의 복잡한 네트워크를 표현할 수 없습니다. 서울의 지하철 노선도, 페이스북의 친구 관계, 웹페이지의 하이퍼링크, 내비게이션의 도로망 등 "어떤 객체들이 서로 얽히고설켜 연결되어 있는 상태"를 수학적이고 논리적으로 모델링하기 위해 탄생한 컴퓨터 과학의 정점이 바로 '그래프(Graph)' 자료구조입니다. 점(Vertex)과 선(Edge)이라는 단 두 가지 요소로 세상의 모든 연결을 추상화하는 그래프의 기초를 파헤쳐 봅니다.
1. 그래프의 해부학: 정점(Vertex)과 간선(Edge)
그래프는 $G = (V, E)$라는 수식으로 표현됩니다. $V$는 점들을 의미하는 정점(Vertex 또는 Node)의 집합이고, $E$는 그 점들을 이어주는 간선(Edge)의 집합입니다. 지하철 노선도로 치면, 강남역이나 홍대입구역 같은 '역' 하나하나가 정점(Vertex)이 되고, 역과 역을 이어주는 '철로'가 간선(Edge)이 됩니다.
1-1. 관계의 성격에 따른 그래프의 종류
- 무방향 그래프(Undirected Graph): 간선에 화살표가 없습니다. A와 B가 친구라면 B도 A의 친구인 양방향 통행(일반적인 도로)을 의미합니다.
- 방향 그래프(Directed Graph): 간선에 화살표가 있습니다. 인스타그램의 '팔로우'처럼 일방통행의 관계를 표현할 때 쓰입니다.
- 가중치 그래프(Weighted Graph): 간선 위에 숫자(비용, 거리, 시간 등)가 적혀 있습니다. 강남역에서 양재역까지 '2분'이 걸린다는 디테일한 정보를 담습니다.
2. 컴퓨터는 그래프를 어떻게 기억할까?
우리는 눈으로 지도를 보지만, 컴퓨터의 메모리는 일직선으로 되어 있습니다. 이 얽힌 관계를 컴퓨터에 우겨넣는 방법에는 두 가지가 있습니다.
2-1. 인접 행렬 (Adjacency Matrix)
2차원 배열(표)을 만들어서, 정점 A에서 정점 B로 가는 길이 있으면 1, 없으면 0을 채워 넣습니다.
장점: A와 B가 연결되어 있는지 물어보면 배열 인덱스 arr[A][B]를 찔러서 단 $O(1)$ 만에 대답할 수 있습니다.
단점: 정점이 10만 개라면 무려 100억 개의 칸을 가진 거대한 배열이 필요하여 메모리가 터져버립니다. 공간 복잡도가 $O(V^2)$이므로 조밀한 그래프에만 씁니다.
2-2. 인접 리스트 (Adjacency List)
각 정점마다 자신과 연결된 진짜 이웃들만 적어둔 연결 리스트(가변 배열)를 따로 매달아 두는 방식입니다. 강남역의 명부에 [양재, 역삼, 교대]만 적어두는 식입니다.
장점: 실제로 존재하는 간선의 개수만큼만 메모리를 쓰므로 매우 효율적($O(V+E)$)입니다. 현실 세계의 대부분의 그래프(지하철 노선 등)는 정점은 많지만 간선은 듬성듬성한 '희소 그래프(Sparse Graph)'이므로, 거의 모든 알고리즘(DFS, BFS, 다익스트라)은 이 인접 리스트 방식으로 구현됩니다.
1. 그래프(Graph)는 객체를 나타내는 정점(Vertex)과 그들의 관계를 나타내는 간선(Edge)으로 이루어진 비선형 자료구조입니다.
2. 간선의 방향 유무와 가중치(비용) 유무에 따라 무방향/방향/가중치 그래프 등 다양하게 모델링할 수 있습니다.
3. 메모리 상에 구현할 때는 두 정점의 연결 여부를 $O(1)$에 확인하는 인접 행렬과, 메모리를 효율적으로 쓰고 탐색에 유리한 인접 리스트 방식을 상황에 맞게 골라 씁니다.