20、图的遍历深度优先遍历和广度优先遍历掌握图的深度优先和广度优先遍历的性质和方法，以及基于邻接矩阵和邻接表存储结构的递归和非递归的算法实现目录20.1概述20.2深度优先遍历20.3深度优先遍历的性质20.4广度优先遍历20.5广度优先遍历的性质20、 图的遍历 从这节起，我们介绍图的一些重要操作的实现，包括遍历、拓扑排序、关键路径等。另有一些重要操作，如最短路径问题、最小生成树问题，由于主要难点在于算法，所以我们安排在后面的算法设计章节中介绍。 图的遍历与树的遍历一样具有十分重要的作用，图的许多其他操作（算法）都与遍历相关。20.1 概述 图的遍历的含意是，从图中某结点出发，按某既定方式访问图中各个可访问到的结点，使每个可访问到的结点恰被访问一次。图的遍历方式有两种：深度优先与广度优先方式，分别对应于树的先根遍历与层序遍历。树中不存在回路，但图中可能有回路。因此，当沿回路进行扫描时，一个结点可能被扫描到多次，可能导致死循环。为了避免这种情形，在遍历中，应为每个结点设立一个访问标志，每扫描到一个结点，要检查它的访问标志，若标志为“未访问”，则按正常方式对其进行处理（如访问或转到它的邻
