Question

我有天早晨准备出门，发现钥匙不见了。昨晚还看到它，所以确定钥匙在家里。一定是我那三岁不到的儿子拿着玩，不知道丢到哪个犄角旮旯去了，问他也说不清楚。我现在必须得找到它，你们说，我应该如何找？介绍我们家的结构，如图7-5-1所示，是最典型的两室两厅一厨一卫一阳台。

图7-5-1

有人说，往小孩子经常玩的地方找找看。OK，我照做了，可惜没找到。然后怎么办？有人说一间一间找，可怎么个找法？是把一间房间翻个底朝天再找下一间好呢，还是先每个房间的最常去的位置找一找，然后再一步一步细化到每个房间的角落？

这是一个大家都可能会面临的问题，不找的东西时常见，需要的东西寻不着。找东西的策略也因人而异。有些人因为找东西没有规划，当一样东西找不到时，往往会反复地找，甚至某些抽屉找个四五遍，另一些地方却一次也没找过。找东西是没有什么标准方法的，不过今天我们学过了图的遍历以后，你至少应该在找东西时，更加科学地规划寻找方案，而不至于手忙脚乱。

图的遍历是和树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traversing Graph）。

树的遍历我们谈到了四种方案，应该说都还好，毕竟根结点只有一个，遍历都是从它发起，其余所有结点都只有一个双亲。可图就复杂多了，因为它的任一顶点都可能和其余的所有顶点相邻接，极有可能存在沿着某条路径搜索后，又回到原顶点，而有些顶点却还没有遍历到的情况。因此我们需要在遍历过程中把访问过的顶点打上标记，以避免访问多次而不自知。具体办法是设置一个访问数组visited[n]，n是图中顶点的个数，初值为0，访问过后设置为1。这其实在小说中常常见到，一行人在迷宫中迷了路，为了避免找寻出路时屡次重复，所以会在路口用小刀刻上标记。

对于图的遍历来说，如何避免因回路陷入死循环，就需要科学地设计遍历方案，通常有两种遍历次序方案：它们是深度优先遍历和广度优先遍历。