<aside> <img src="/icons/list-indent_lightgray.svg" alt="/icons/list-indent_lightgray.svg" width="40px" />
Table Of Contents
</aside>
그래프는 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 데이터 자료구조이다.
정점(Vertex, Node) 집합과 간선(Edge) 집합으로 표현할 수 있다.
실제 소프트웨어 사용 예로는 지하철 노선도, 페이지랭크(PageRank) 알고리즘이 있다.
| 용어 | 의미 |
|---|---|
| 정점(vertex, node) | 정점, 데이터 |
| 간선(edge) | 노드, 정점 간의 관계나 흐름 |
| 인접 정점(adjacent vertex) | 간선으로 연결된 정점 |
| 차수(degree) | 인접 정점의 개수 |
| 사이클(cycle) | 그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분 |
그래프는 방향성, 가중치, 연결 상태, 순환 특성에 따라 종류를 구분할 수 있다.
흐름을 표현하는 방향성
간선은 방향을 가질 수도 있고 없을 수도 있다.
방향이 있는 간선을 포함하면 방향 그래프, 방향이 없는 간선을 포함하면 무방향 그래프라고 한다.
이때 방향 그래프는 어느 한쪽으로만 간선이 있는 것이 아니라 서로 반대를 가리키는 간선이 있을 수도 있다.