트리는 계층적 데이터를 표현하는 좋은 방법이지만, 하나의 노드에서 다른 노드로 이동하는 경로가 하나만 존재하기 때문에 원형 또는 순환적인 종속성을 표현할 수 없습니다. 그러나 실생활에서 순환 구조를 사용하여 표현해야 하는 시나리오도 많이 존재합니다. 예를 들어 도로망을 생각해보면, 특정 장소(노드)에서 다른 장소로 이동하기 위한 다양한 경로가 존재할 수 있습니다. 이러한 경우에는 그래프(graph) 구조를 사용하는 것이 더욱 바람직합니다.

그래프는 노드 데이터뿐만 아니라 노드 사이의 에지 데이터도 저장해야 합니다. 도로망을 예로 들면 각각의 노드(장소)에 다른 어떤 노드들이 연결되어 있는지에 대한 정보를 가지고 있어야 합니다. 이런 방법으로 필요한 모든 노드와 에지가 있는 그래프를 만들 수 있으며, 이러한 그래프를 비가중 그래프(unweighted graph)라고 합니다. 에지에 가중치(weight) 또는 더 많은 정보를 부여할 수도 있습니다. 예를 들어 도로망을 구성할 때 각각의 에지(도로)에 노드(장소)와 노드 사이의 거리를 저장할 수 있습니다. 이러한 형태의 그래프를 가중 그래프(weighted graph)라고 합니다. 도로망을 가중 그래프 형태로 표현함으로써 특정 장소에서 다른 장소로 이동하는 최단 거리 경로 탐색 같은 문제에서 이 그래프를 활용할 수 있습니다.

그래프는 방향성이 있는 그래프와 방향성이 없는 그래프로 구분할 수 있습니다. 무방향 그래프(undirected graph)는 에지가 양방향임을 의미합니다. 양방향이라 함은 대칭적인, 또는 상호 교환적인 속성을 나타냅니다. 도로망을 예로 들면, A와 B 장소 사이에 양방향 에지가 있다는 것은 A에서 B로 이동할 수 있고, 동시에 B에서 A로도 이동할 수 있음을 나타냅니다. 만약 어떤 도로가 일방통행으로 제한되어 있다면 이때는 방향 그래프(directed graph)를 사용해야 합니다. 방향 그래프에서 양방향 에지를 표현하려면 A에서 B, 그리고 B에서 A로 향하는 두 개의 에지를 사용해야 합니다. 이 책에서는 주로 양방향 그래프에 초점을 맞출 것입니다. 그러나 여기서 설명하는 무방향 그래프의 구조와 순회 방법은 방향 그래프에도 적용할 수 있고, 다만 그래프에 에지를 추가하는 방법만 달라집니다.

그래프는 순환적 에지를 가질 수 있고 특정 노드에서 다른 노드로 이동하는 방법이 여러 개 있을 수 있으므로 각 노드를 고유하게 식별해야 합니다. 이를 위해 각 노드에 고유한 ID를 부여할 수 있습니다. 그래프의 데이터를 표현하기 위해 반드시 트리의 노드 같은 구조를 사용해야 하는 것은 아닙니다. 실제로 STL 컨테이너를 이용하여 그래프를 표현할 수 있습니다.