우리가 매일 사용하는 지하철 노선도, 페이스북이나 인스타그램의 친구 관계, 내비게이션의 최단 경로 찾기. 이들의 공통점은 무엇일까요? 바로 점과 선으로 연결된 네트워크 구조를 가지고 있다는 것입니다. 컴퓨터 과학에서는 이러한 연결 망을 수학적으로 모델링하여 그래프(Graph)라고 부릅니다. 그래프는 단순히 그림을 그리는 것이 아니라, 복잡하게 얽힌 데이터 간의 관계를 표현하고 문제를 해결하는 가장 강력한 도구입니다. 오늘은 그래프 이론의 기초가 되는 핵심 용어들과 그 구조적 특징을 완벽하게 정리해 드리겠습니다.
1. 그래프(Graph)란 무엇인가?
그래프는 사물(Entity)과 그 사물 간의 관계(Relationship)를 표현하는 비선형 자료구조입니다. 수학적으로는 $G = (V, E)$로 표현합니다. 여기서 $V$는 정점(Vertex)의 집합, $E$는 간선(Edge)의 집합을 의미합니다. 쉽게 말해 그래프는 점과 그 점들을 잇는 선들의 모음입니다.
1-1. 그래프의 구성 요소
- 정점 (Vertex / Node): 그래프를 구성하는 가장 기본적인 객체입니다. 지하철 노선도에서 '역(Station)'에 해당하며, 페이스북에서는 '사용자(User)'에 해당합니다.
- 간선 (Edge / Link): 두 정점을 연결하는 선입니다. 정점 간의 관계를 나타냅니다. 지하철의 '선로', SNS의 '친구 맺기'가 이에 해당합니다.
- 인접 (Adjacency): 두 정점이 간선으로 직접 연결되어 있을 때, "두 정점은 인접해 있다"고 말합니다.
- 차수 (Degree): 하나의 정점에 연결된 간선의 개수입니다. 인스타그램 팔로워 수가 많다는 것은 해당 정점의 차수가 높다는 뜻입니다.
2. 그래프의 다양한 종류
그래프는 간선의 성격에 따라 여러 가지 형태로 나뉩니다. 해결하려는 문제의 특성에 맞춰 적절한 그래프 모델을 선택해야 합니다.
2-1. 방향성에 따른 분류
- 무방향 그래프 (Undirected Graph): 간선에 방향이 없는 그래프입니다. A와 B가 연결되어 있다면, A에서 B로 갈 수도 있고 B에서 A로 갈 수도 있습니다. (예: 양방향 통행 도로, 악수하기)
- 방향 그래프 (Directed Graph): 간선에 화살표가 있어 한쪽으로만 갈 수 있는 그래프입니다. 'A -> B'는 가능하지만 'B -> A'는 불가능할 수 있습니다. (예: 일방통행 도로, 인스타그램 팔로우, 웹사이트 하이퍼링크)
2-2. 가중치에 따른 분류
- 가중치 그래프 (Weighted Graph): 간선에 비용이나 거리를 나타내는 숫자(가중치)가 부여된 그래프입니다. 내비게이션에서 '거리'나 '소요 시간'을 계산할 때 사용됩니다.
- 비가중치 그래프: 모든 간선의 가치가 동일한 그래프입니다. 단순히 연결 여부만 중요합니다.
3. 컴퓨터는 그래프를 어떻게 저장할까?
우리가 눈으로 보는 그림을 컴퓨터 메모리에 저장하는 방법은 크게 두 가지가 있습니다.
3-1. 인접 행렬 (Adjacency Matrix)
정점의 개수가 N개일 때, N x N 크기의 2차원 배열을 만들어 연결 관계를 0과 1로 표시하는 방법입니다.
- 장점: 두 정점이 연결되어 있는지 확인하는 속도가 O(1)로 매우 빠릅니다. `matrix[i][j]`가 1인지만 보면 됩니다.
- 단점: 정점은 많은데 간선이 적은 경우(희소 그래프), 대부분의 공간이 0으로 채워져 메모리 낭비가 심합니다.
3-2. 인접 리스트 (Adjacency List)
각 정점마다 연결 리스트를 매달아, 자신과 연결된 정점들만 저장하는 방법입니다.
- 장점: 실제로 연결된 정보만 저장하므로 메모리를 효율적으로 사용합니다. 대부분의 알고리즘 문제에서 선호되는 방식입니다.
- 단점: 두 정점의 연결 여부를 확인하려면 리스트를 탐색해야 하므로 속도가 인접 행렬보다 느릴 수 있습니다.
4. 그래프 탐색의 핵심: DFS와 BFS
그래프의 모든 정점을 한 번씩 방문하는 것을 '순회' 또는 '탐색'이라고 합니다. - 깊이 우선 탐색 (DFS): 미로 찾기처럼 갈 수 있는 끝까지 들어갔다가 막히면 되돌아 나오는 방식 (스택/재귀 사용). - 너비 우선 탐색 (BFS): 호수에 던진 돌의 파동처럼 가까운 이웃부터 차례대로 방문하는 방식 (큐 사용). 최단 경로를 찾을 때 주로 쓰입니다.
1. 그래프는 정점(Node)과 간선(Edge)으로 이루어진 비선형 구조로, 네트워크 관계를 표현합니다.
2. 방향 유무와 가중치 유무에 따라 다양한 종류로 나뉘며, 문제 상황에 맞게 모델링해야 합니다.
3. 구현 방식에는 인접 행렬(빠른 조회, 메모리 큼)과 인접 리스트(메모리 절약)가 있습니다.