그래프(Graph)
그래프(Graph)란 무엇인가
그래프는 정점과 정점 사이의 연결 관계를 표현하는 자료구조다.
데이터 하나하나를 순서대로 나열하는 것이 아니라, 서로 어떻게 연결되어 있는지를 표현하는 데 초점이 맞춰져 있다. 그래서 그래프는 트리와 마찬가지로 비선형 자료구조에 속한다.
앞서 배운 스택이나 큐 같은 선형 자료구조는 “어떤 순서로 데이터를 넣고, 어떤 순서로 꺼낼 것인가”가 핵심이었다. 반면 그래프는 저장 순서보다는 관계와 구조 자체를 표현하는 것이 목적이다. 이 때문에 사람 관계, 지도, 네트워크, 추천 시스템처럼 “연결”이 중요한 문제에서 그래프가 자주 사용된다.
그래프를 예시로 이해해보기
사람 관계를 예로 들어보자.
- 민수와 영희는 친구다.
- 영희와 철수는 친구다.
- 철수와 지연은 친구다.
이를 그래프로 표현하면 다음과 같다.
민수 - 영희 - 철수 - 지연여기서 사람 한 명 한 명이 노드(Node)이고, 친구 관계가 간선(Edge)이다. 영희와 민수처럼 간선으로 직접 연결된 관계를 인접 노드라고 부른다. 이처럼 그래프는 “누가 누구와 연결되어 있는가”를 직관적으로 표현할 수 있다.
그래프의 기본 용어
- 노드(Node) / 정점(Vertex): 그래프를 이루는 각각의 데이터
- 간선(Edge): 노드와 노드 사이의 연결 관계
- 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드
유방향 그래프와 무방향 그래프
그래프는 간선에 방향이 있는지에 따라 두 가지로 나뉜다.
- 유방향 그래프: 간선에 방향이 있어 한쪽 방향으로만 이동할 수 있다.
- 무방향 그래프: 간선에 방향이 없고, 양쪽으로 자유롭게 이동할 수 있다.
이번 글에서는 친구 관계처럼 상호 관계를 표현하기 쉬운 무방향 그래프만 다룬다.
그래프를 표현하는 두 가지 방법
그래프를 컴퓨터에서 표현하는 방법에는 대표적으로 인접 행렬과 인접 리스트가 있다.
인접 행렬 (Adjacency Matrix)
인접 행렬은 그래프의 연결 관계를 2차원 배열로 표현하는 방식이다.
graph = [
[False, True, False, False],
[True, False, True, False],
[False, True, False, True ],
[False, False, True, False]
]graph[i][j]가 True라면 i번 노드와 j번 노드가 연결되어 있다는 의미다.
이 방식의 가장 큰 장점은 두 노드가 연결되어 있는지 바로 확인할 수 있다는 점이다.
graph[1][2] # O(1)하지만 단점도 있다.
노드가 N개라면 모든 조합의 연결 여부를 저장해야 하므로 공간 복잡도는 O(N²)이 된다.
그래프가 커질수록 메모리 사용량이 급격히 늘어난다.
인접 리스트 (Adjacency List)
인접 리스트는 각 노드마다 연결된 노드만 따로 저장하는 방식이다.
graph = {
0: [1],
1: [0, 2],
2: [1, 3],
3: [2]
}이 방식에서는
• 노드 N개
• 실제 연결된 간선 M개
이 방식은 실제로 존재하는 연결만 저장하기 때문에 공간 효율이 좋다.
공간 복잡도는 O(N + M) 수준이다.
다만 두 노드가 연결되어 있는지 확인하려면, 해당 노드의 리스트를 직접 확인해야 한다. 따라서 연결 여부 확인은 최악의 경우 O(M)가 걸릴 수 있다.
인접 행렬과 인접 리스트의 차이
두 표현 방식의 차이는 결국 시간과 공간의 선택 문제다.
- 인접 행렬
- 연결 여부 확인: 빠름 (O(1))
- 공간 사용량: 큼 (O(N²)) - 인접 리스트
- 연결 여부 확인: 느릴 수 있음 (최악 O(M))
- 공간 사용량: 효율적 (O(N + M))
그래프가 촘촘하게 연결된 경우에는 인접 행렬이,
그래프가 연결이 적은 경우에는 인접 리스트가 더 적합하다.
정리
1. 그래프는 연결 관계를 표현한다
2. 인접 행렬과 인접 리스트는 시간과 공간의 트레이드오프다
3. 인접 리스트의 공간 복잡도는 O(N + M)이다그래프는 데이터를 나열하는 자료구조가 아니라, 데이터 간의 관계를 표현하는 자료구조다.
노드와 간선이라는 개념만 이해하면 구조 자체는 단순하지만, 활용 범위는 매우 넓다.
