목차
그래프는 정점(node 또는 vertex)과 간선(edge)로 이루어진 자료구조이다.
사실 트리는 그래프의 일종이다. 하지만, 그래프는 트리와 달리 정점마다 간선이 존재하지 않을 수도 있으며, 루트 노드와 부모 노드, 자식 노드 개념이 존재하지 않는다.
위의 그림은 정점이 3개이고, 간선이 3개인 그래프이다.
그래프는 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조이다. 그래서 그래프는 실생활에서 지하철 노선도 최단 경로, 도로, 선수 과목 등에 쓰이고 있다.
| 용어 | 뜻 |
|---|---|
| 정점(Vertex or Node) | 데이터를 저장하는 위치 |
| 간선(Edge) | 정점(노드)를 연결하는 선. 링크(Link) 또는 브랜치(branch) 로도 불린다. |
| 인접 정점(adjacent vertex) | 간선에 의해 직접 연결된 정점을 의미한다. 위의 그림에서 1과 2는 인접 정점이다. |
| 단순 경로(simple path) | 경로 중에서 반복되는 정점이 없는 경우를 의미한다. 한붓 그리기와 같이 같은 간선을 지나가지 않는 경로를 의미한다. |
| 차수(degree) | 무방향 그래프에서 하나의 정점에 인접한 정점의 수를 의미한다. 1의 차수는 2이다. |
| 진출 차수(in-degree) | 방향 그래프에서 외부로 향하는 간선의 수를 의미한다. |
| 진입 자수(out-degree) | 방향 그래프에서 외부에서 들어오는 간선의 수를 의미한다. |
| 경로 길이(path length) | 경로를 구성하는데 사용된 간선의 수를 의미한다. |
| 사이클(cycle) | 단순 경로의 시작 정점과 종료 정점이 동일한 경우를 의미한다. |
.png)
무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프이다.
.png)
방향 그래프는 두 정점을 연결하는 간선에 방향이 존재하는 그래프이다.
간선이 가리키는 방향으로만 이동할 수 있다.