그래프란 무엇인가?
그래프(Graph)는 대표적인 비선형(non-linear) 자료구조입니다. 그래프는 데이터를 노드(정점)로 표현하고, 데이터 간의 관계를 간선(Edge)으로 나타냅니다. 하나의 그래프 G는 두 가지 구성 요소를 가지는데, 바로 정점(Vertex)과 간선(Edge)입니다. 정점은 집합 V로, 간선은 집합 E로 표현되며, 따라서 그래프는 일반적으로 G(V, E)와 같이 표기합니다.
아래 예시를 통해 그래프의 개념을 좀 더 구체적으로 살펴보겠습니다.
위 그래프에는 5개의 정점과 5개의 간선이 존재하며, 모든 간선은 방향성을 가지고 있습니다. 예를 들어 정점 B와 D를 연결하는 간선을 보면, 시작 정점(source)은 B이고 도착 정점(destination)은 D입니다. 따라서 B에서 D로는 이동할 수 있지만, 반대로 D에서 B로는 직접 이동할 수 없습니다.
그래프는 비선형 구조이며 규칙적인 형태가 없기 때문에, 메모리에 저장하기 위해서는 별도의 표현 방식이 필요합니다. 그래프를 표현하는 대표적인 방법은 다음 세 가지입니다.
- 인접 행렬(Adjacency Matrix) 표현
- 간선 리스트(Edge List) 표현
- 인접 리스트(Adjacency List) 표현
1. 인접 행렬(Adjacency Matrix) 표현
그래프는 인접 행렬을 사용하여 표현할 수 있습니다. 인접 행렬은 0과 1로만 구성된 이진 행렬(binary matrix)이자 정방행렬(square matrix)로, i번째 행에서 j번째 열에 해당하는 위치에 간선이 존재하면 그 값을 1로 표시합니다. 만약 무방향 그래프를 인접 행렬로 표현하면, 행렬은 항상 대각선을 기준으로 대칭(symmetric) 형태가 됩니다.
2. 간선 리스트(Edge List) 표현
그래프는 1차원 배열을 이용해서도 표현할 수 있으며, 이를 간선 리스트(edge list)라고 부릅니다. 이 표현 방식에서는 각 간선마다 첫 번째 요소에 시작 정점을, 두 번째 요소에 도착 정점을 저장합니다. 위 예시 그래프에는 총 5개의 간선이 존재합니다. 참고로 무방향 그래프를 간선 리스트로 표현할 경우에는 간선 정보가 양방향으로 모두 저장되어야 하므로, 요소의 개수가 두 배가 됩니다.
3. 인접 리스트(Adjacency List) 표현
인접 리스트는 또 다른 그래프 표현 방식으로, 연결 리스트(Linked List)를 기반으로 합니다. 이 방식에서는 각 정점(노드)이 해당 정점과 직접 연결된 인접 정점들의 목록을 가지고 있습니다. 리스트의 끝에는 NULL 값이 연결되어 있어, 해당 리스트가 여기서 끝난다는 것을 알 수 있습니다.
