그래프(graph)는 네트워크를 표현하는 자료 구조로, 정점(vertex)이라 부르는 노드와 정점 사이를 연결하는 간선(edge)의 집합으로 구성됩니다. 간선은 두 노드 간의 경로(path)이며, 방향성이 있거나(directed) 없을(undirected) 수 있습니다. 경로가 방향성이 있으면 한 방향으로만 이동할 수 있고 방향성이 없으면 양방향으로 이동할 수 있습니다. 그리고 간선과 관련된 비용이 발생할 수 있습니다.

▲ 그림 3-11 정점과 간선으로 이루어진 그래프