그래프(Graph)는 대표적인 비선형 자료구조입니다. 그래프는 노드(Node)를 사용하여 데이터를 표현하고, 에지(Edge)를 통해 노드 사이의 관계를 나타냅니다.
그래프 G는 크게 두 가지 요소로 구성됩니다. 바로 정점(Vertex)과 간선(Edge)입니다. 정점은 집합 V로 표현되고, 간선은 집합 E로 표현됩니다. 따라서 그래프는 일반적으로 G(V, E)와 같이 표기합니다. 아래 예시를 통해 그래프의 개념을 좀 더 구체적으로 살펴보겠습니다.
방향 그래프의 이해
위 그래프에는 다섯 개의 정점과 다섯 개의 간선이 존재하며, 모든 간선은 방향(Directed)을 가지고 있습니다. 예를 들어, 정점 B와 D를 연결하는 간선을 선택한다면 시작 정점(Source Vertex)은 B이고, 도착 정점(Destination Vertex)은 D가 됩니다. 즉, B에서 D로는 이동할 수 있지만, 반대로 D에서 B로는 이동할 수 없습니다.
그래프를 메모리에 표현하는 방법
그래프는 비선형 구조이기 때문에 배열처럼 규칙적인 형태를 가지지 않습니다. 따라서 그래프를 컴퓨터 메모리에 저장하고 활용하기 위해서는 별도의 표현 방식이 필요합니다. 대표적인 표현 방식은 다음과 같습니다.
- 인접 행렬(Adjacency Matrix) 표현
- 간선 목록(Edge List) 표현
- 인접 리스트(Adjacency List) 표현
이 글에서는 그중 인접 리스트 표현 방식에 대해 자세히 알아보겠습니다.
인접 리스트(Adjacency List) 표현이란?
인접 리스트는 이름 그대로 각 정점에 인접한 정점들을 목록 형태로 저장하는 방식입니다. 이 표현 방식은 연결 리스트(Linked List)를 기반으로 동작합니다.
핵심 원리는 다음과 같습니다. 그래프의 각 정점(Node)마다 하나의 리스트를 할당하고, 해당 리스트에는 그 정점과 직접 연결된 정점들만을 순서대로 담습니다. 그리고 각 리스트의 마지막 노드는 null 값과 연결되어, 해당 리스트의 끝임을 명확하게 표시합니다.
인접 리스트의 장점
인접 리스트 방식은 실제로 연결된 간선 정보만 저장하기 때문에, 간선의 수가 적은 희소 그래프(Sparse Graph)에서 메모리를 매우 효율적으로 사용할 수 있습니다. 또한 특정 정점에 연결된 모든 이웃 정점을 빠르게 탐색할 수 있다는 점에서, 너비 우선 탐색(BFS)이나 깊이 우선 탐색(DFS) 같은 그래프 순회 알고리즘에 널리 활용됩니다.