그래프는 컴퓨터 과학에서 기본 자료 구조.

그래프 구는 특정 계산을 최적화하기 위해 설계된 것이 아니라 데이터 자체로부터 자연스럽게 발생한다. 즉, 그래프는 자신이 나타내는 데이터를 반영한다.

그래프는 데이터의 구조로부터 새로운 알고리즘 설계를 이끌어내는 방법.

• 최단 경로를 찾는 데이크스트라(Dikstra) 알고리즘
• 최소 스패닝 트리(minimum cost spanning tree)를 찾는 프림의 알고리즘(Prim’s algorithm)
• 위상 정렬(topological sort)을 수행하는 칸의 알고리즘(Kahn’s algorithm)

15.1 그래프 소개

그래프는 노드의 집합과 간선(edge, 에지)의 집합으로 구성.

• 각 간선은 두 노드 사이를 연결한다.

그래프의 간선은 간선에 방향이 있는지 등 현실 세계의 복잡성을 데이터로 잡아내기 위한 추가 속성을 포함할 수 있다.

• 무방향 간선(undirected edge)은 양방향 관계를 나타낸다.
• 유방향 간성(directed edge, 방향 간선 또는 방향성 간선)은 한 방향으로의 흐름을 나타낸다.

우리는 무방향성인 접근을 나타내기 위해 두 노드 사이에 서로 반대 방향을 가리키는 두 개의 간선을 사용한다.

방향성 간선은 작업 사이의 의존 관계(dependency)와 같은 추상적인 문제를 모델링할 수 있게 해준다.

노드를 작업의 집합으로 지정하고, 방향 간선을 사용해 작업 사이의 의존 관계를 나태날 수 있다.

간선은 단계들 사이의 의존 관계를 나타낸다.

간선의 가중치(weight)를 부여하면 그래프의 모델링 능력이 더 커진다.

• 가중치가 있는 간선은 노드 사이의 연결 유무뿐 아니라 그 연결의 비용까지 나타낸다.