문제를 어떻게 해결할지 알아보기 전에 미로를 어떻게 일반적인 방법으로 표현할지를 생각해 보아야 한다. 앞에서 묘사한 대로 미로는 방과 방 사이를 연결하는 통로로 구성된다. 이 미로의 구조를 탐구하다 보면 더욱더 흥미로워진다고 했다. 사실, 미로는 객체와 객체 사이를 연결하는 구조와 유사하다. 현실 세계의 많은 것이 객체와 객체 간 연결로 표현되므로 이는 아마도 가장 기본적인 자료 구조일 것이다. 우리는 이 구조를 그래프(graph)라고 하는데, 그래프는 노드(node)와 노드 사이를 연결하는 링크(link)의 집합으로 정의된다. 달리 얘기하면 그래프는 정점(vertex)과 간선(edge)의 집합이다. 간선은 두 정점을 연결한다. 두 간선이 공통으로 한 노드를 공유하는 연속한 간선들을 경로(path)라고 한다.

그림 2-2는 노드 1을 통해 노드 0과 2를 연결하는 경로를 보여준다. 한 경로에 있는 간선의 수를 길이(length)라고 하는데, 간선 하나는 길이 1인 경로다. 경로 하나가 2개의 노드 사이에 있으면 두 노드는 연결되었다(connected)고 한다. 간선들에 방향성이 있으면 방향 그래프(directed graph, 간단히 digraph)라고 하고, 그렇지 않으면 무방향 그래프(undirected graph)라고 한다. 그림 2-5에서 왼쪽은 무방향 그래프를, 오른쪽은 방향 그래프를 보여준다. 그림에서 보듯이 한 노드에서 시작하거나 끝나는 많은 간선이 있는데, 이렇게 한 노드에 인접한 간선의 수를 간선의 차수(degree)라고 한다. 방향 그래프에서는 한 노드로 들어오는 간선의 수인 입력 차수(in-degree)와 한 노드로부터 나가는 간선의 수인 출력 차수(out-degree)가 있다. 그림 2-5의 (a)에서 모든 노드의 차수는 3이고, 그림 2-5의 (b)에서 노드 3의 입력 차수는 2, 출력 차수는 1이다.

▲ 그림 2-5 무방향 그래프와 방향 그래프