图的遍历

与树的遍历类似，图的遍历就是通过某一种方法逐个访问图中的每一个顶点。但是，图的遍历比树的遍历要复杂得多，因为图中任一顶点都可能和其他顶点相邻接，这样，从图中的某 个顶点到达其余顶点就可能存在多条路径。当顺着某一路径访问过某个顶点后，可能还会顺着另一路径访问到该顶点。为了避免同一顶点在遍历时被多次访问，可以考虑设置一个数组 isTrav[n]来记录某个顶点是否已被访问过，首先设置数组各元素的初始值为0或False，当某个顶点被访问过，则设置对应的数组元素值为1或True。在访问顶点i时，先判断数组isTrav[i]中的 值，若其值为1或True，则继续访问路径的下一个顶点；若其值为0或False，则访问当前顶点（进行相应的处理），然后继续访问路径的下一个顶点。

 图的遍历操作是求解图的连通性问题，进行拓扑排序，求解最短路径，求解关键路径等运算的基础。

提示 数组isTrav在邻接矩阵的结构中已作为图结构的一个成员进行了定义。 

常用的图遍历方法有两种：广度优先法和深度优先法。

1．广度优先遍历 

广度优先遍历类似于树的按层次遍历，具体过程如下： 

（1）从isTrav数组中选择一个未被访问的顶点Vi ，将其标记为已访问。 

（2）接着依次访问Vi 的所有未被访问的邻接点，并标记为已被访问过。 

（3）从这些邻接点出发进行广度优先遍历，直至图中所有和Vi 有路径相通的顶点都被访问过。 

（4）重复步骤1至步骤3的操作，直至所有顶点都被访问过。 从以上步骤可看出，广度优先遍历是以Vi 为起始访问点，依次访问和Vi 有路径相通且未被访问的顶点。

广度优先遍历不是递归过程。在遍历过程中，先被访问的顶点，其邻接点也先被访问，所以在算法的实现时需要设置一个队列，用来依次记住被访问过的 顶点。 

注意 算法开始时，将初始顶点Vi访问后进入队列，然后循环处理队列中的元素。每从队列中删除一个元素，就依次访问该元素的每一个未被访问过的邻接点，并将这些邻接点进入 队列。这样，当队列为空时，表明所有与初始访问顶点有路径相通的顶点都已被访问。然后再从isTrav中找出一个未被访问的顶点，重复该操作，直到所有顶点都被访问过，完成遍历操 作。

2、深度优先遍历 

深度优先遍历方法类似于树的先序遍历，具体过程如下： 

（1）从isTrav数组中选择一个未被访的顶点Vi ，将其标记为已访问。 

（2）接着从Vi 的一个未被访问过的邻接点出发进行深度优先遍历。 

（3）重复步骤2，直至图中所有和Vi 有路径相通的顶点都被访问过。 

（4）重复步骤1至步骤3的操作，直至所有顶点都被访问过。 

提示 从上面的描述可以看出，深度优先遍历是一个递归过程。