3-1. Graph란?
3-1-a. 용어 정의
그래프(Graph)는 관계를 표현하기 위해 필요하고 사용하는 자료구조입니다. 이런 그래프는 관계 표현을 위해 정점(Node, Vertex)과 간선(Edge, Link) 을 사용합니다.
- 정점은 단순히 정보를 담을 수도 있고 상태를 담을 수도 있습니다.
- 간선은 정보나 상태를 연결합니다. 거리, 비용 등 가중치(Weight)를 표시할 수 있습니다.
간선의 연결 상태에 따라서는 다음과 같이 분류할 수 있습니다.
- 무향 그래프 : 방향이 없는 그래프
- 유향 그래프 : 방향이 있는 그래프
그리고 이런 정점과 간선의 관계는 다음과 같은 정의가 있습니다.
- 차수(degree) : 한 정점에 이어져 있는 간선의 수
- 입력 차수(indegree) : 유향그래프에서 정점으로 들어오는 간선
- 출력 차수(outdegree) : 유향그래프에서 정점에서 나가는 간선
- 인접(adjacent) : 정점 사이에 간선이 있는 경우
유향그래프 중에 cycle이 없는 경우는 DAG(Directed Acyclic Graph)라고 부르는 데, 위상정렬 등의 알고리즘에서 사용합니다.
3-1-b. 구현 및 표현 방법
그래프는 필요에 따라 구현 방법이 다르고 다음과 같이 나눌 수 있습니다.
-
인접행렬 : N by N 행렬에서 연결 상태를 표시하는 방법
-
인접리스트 : 길이 N 배열에 각 index별로 연결된 노드만 저장
비교적 연결이 적은(sparse)한 그래프의 경우에는 인접리스트를 많이 사용합니다. 인접행렬은 반드시 \(O(N^2)\)의 공간복잡도를 가지는 반면, 인접리스트는 간선의 개수인 \(O(E)\) 시간복잡도를 가지게 됩니다.
이 표기법은 후에 알고리즘 문제를 해결하며 익혀보겠습니다.