9.4 요약¶
1. 핵심 정리¶
- 그래프는 정점과 간선으로 이루어지며, 정점 집합과 간선 집합으로 표현할 수 있다.
- 선형 관계(연결 리스트)와 분할 정복 관계(트리)에 비해 네트워크 관계(그래프)는 자유도가 높아 더 복잡하다.
- 방향 그래프의 간선에는 방향이 있고, 연결 그래프에서는 모든 정점에 도달할 수 있으며, 가중 그래프의 각 간선에는 가중치 변수가 있다.
- 인접 행렬은 행렬로 그래프를 표현한다. 각 행(열)은 정점 하나를, 행렬 원소는 간선을 나타내며, \(1\) 또는 \(0\)으로 두 정점 사이에 간선이 있는지 표시한다. 인접 행렬은 추가, 삭제, 조회, 수정 연산이 매우 효율적이지만 공간을 많이 차지한다.
- 인접 리스트는 여러 연결 리스트로 그래프를 표현한다. \(i\) 번째 연결 리스트는 정점 \(i\)에 대응하고, 해당 정점의 모든 인접 정점을 저장한다. 인접 행렬보다 공간을 절약하지만, 간선을 찾으려면 연결 리스트를 순회해야 하므로 시간 효율이 낮다.
- 인접 리스트 안의 연결 리스트가 너무 길면 레드-블랙 트리나 해시 테이블로 바꾸어 조회 효율을 높일 수 있다.
- 알고리즘의 관점에서 보면 인접 행렬은 '공간을 더 써서 시간을 절약'하고, 인접 리스트는 '시간을 더 써서 공간을 절약'한다.
- 그래프는 소셜 네트워크나 지하철 노선 등 다양한 현실 시스템을 모델링하는 데 사용할 수 있다.
- 트리는 그래프의 특수한 경우이며, 트리 순회도 그래프 순회의 특수한 경우다.
- 그래프의 너비 우선 순회는 가까운 곳에서 먼 곳으로 한 층씩 확장하는 탐색 방식이며, 보통 큐로 구현한다.
- 그래프의 깊이 우선 순회는 먼저 끝까지 나아가고 더 갈 곳이 없으면 되돌아오는 탐색 방식이며, 보통 재귀로 구현한다.
2. Q & A¶
Q: 경로는 정점의 순서로 정의하는가, 간선의 순서로 정의하는가?
위키백과의 언어별 정의는 서로 다르다. 영어판에서는 '경로는 간선의 순서'라고 하고, 중국어판에서는 '경로는 정점의 순서'라고 한다. 영어판 원문을 옮기면 다음과 같다. '그래프 이론에서 그래프의 경로는 정점의 나열을 연결하는 간선의 유한하거나 무한한 나열이다.'
이 절에서는 경로를 정점의 순서가 아니라 간선의 순서로 본다. 두 정점 사이에 여러 간선이 연결될 수 있으며, 이때 각 간선은 각각 하나의 경로에 해당하기 때문이다.
Q: 비연결 그래프에는 순회할 수 없는 정점이 있는가?
비연결 그래프에서는 한 정점에서 출발했을 때 도달할 수 없는 정점이 하나 이상 존재한다. 그래프의 모든 연결 요소를 순회하려면 시작점을 여러 개 설정해야 한다.
Q: 인접 리스트에서 '해당 정점과 연결된 모든 정점'의 순서에 제약이 있는가?
순서는 자유롭다. 하지만 실제 응용에서는 지정한 규칙에 따라 정렬해야 할 수도 있다. 예를 들어 정점이 추가된 순서나 정점 값의 크기순으로 정렬하면, '특정 기준에서 최댓값이나 최솟값을 가진' 정점을 빠르게 찾는 데 도움이 된다.