图
如何解决探索迷宫问题之前，我们必须解决迷宫的一般性表示方法。回忆我们曾经描述迷宫的方式，它们由房间和房间之间的廊道组成。我们暗示过，当认识到迷宫与其他结构相似时，问题就变得更有趣了。实际上，迷宫与任何由对象和对象间的连接组成的东西是相似的。
这是一种基础数据结构，可能是所有数据结构中最基础的，因为现实世界中很多事物都可以表示为对象和对象间的连接。这种结构被称为「图」（graph）。
一个简洁的定义是：图就是一个节点（node）与其之间的连接（link）组成的一个集合。你可以使用术语「顶点」（vertex，复数形式为vertices）和「边」（edge）。一条边连接恰好有两个顶点。一个边的序列中，如果每两条相邻边都有公共顶点，则我们称之为「路径」（path）。因此，在图2-2中有一条从顶点0到2经由顶点1的路径。一条路径中边的条数称为其长度（length）。一条边就是一条长度为1的路径。如果两个顶点间存在一条路径，则我们说两个顶点是「连接的」（connected）。
在特定的图中，我们可能希望边是有方向的，这种图称为「有向图」（directedgraph，或简写为digraph）。否则，就是「无向图」（undirectedgraph）。图2-5左边是一个无向图，右边是一个有向图。如你所见，可能有多条边从同一个顶点发出或指向同一个顶点。一个顶点邻接边的数目称为它的度（degree）。在有向图中，度分为「入度」（in-degree），即入射边的数目，以及「出度」（out-degree），即出射边的数目。在图2-5a中，所有顶点的度都恰为3。在图2-5b中，最右边的顶点的入度为2，为1。
图的应用可以撑起一整套丛书：令人惊讶的是有这么多事物可用图表示，这么多问题可用图的术语描绘，又有这么多用来求解图相关问题的算法。其原因是，如我们刚刚发现的，很多事物都是由对象及对象间的连接组成的。这值得进一步