6.3图的遍历 从图中某一顶点出发访遍图中其余顶点,且每个顶点 仅被访问一次,这一过程叫图的遍历 由于图中任一顶点都可能和其余的顶点相邻接,故图 的遍历比树的遍历要复杂的多.表现之一,是从某一顶点 出发,沿某条路经搜索后,又回到出发的顶点上,为避免 同一顶点被访问多次,在遍历图的过程中,必须记下每个 已被访问过的顶点.下面介绍两种通常用的遍历图的方法 深度优先搜索法和广度优先搜索法.这两种方法对无向图 和有向图都是适用的 、深度优先搜索法 深度优先搜索遍历图类似于树的前序遍历,其过程是 设初态为图中所有顶点均未被访问过,则从图中某个顶点 V出发,访问此顶点,然后依次从v的未被访问的邻接点6. 3 图的遍历 从图中某一顶点出发访遍图中其余顶点, 且每个顶点 仅被访问一次, 这一过程叫图的遍历. 由于图中任一顶点都可能和其余的顶点相邻接, 故图 的遍历比树的遍历要复杂的多. 表现之一, 是从某一顶点 出发, 沿某条路经搜索后, 又回到出发的顶点上, 为避免 同一顶点被访问多次, 在遍历图的过程中, 必须记下每个 已被访问过的顶点. 下面介绍两种通常用的遍历图的方法 深度优先搜索法和广度优先搜索法. 这两种方法对无向图 和有向图都是适用的. 一﹑深度优先搜索法 深度优先搜索遍历图类似于树的前序遍历, 其过程是 设初态为图中所有顶点均未被访问过, 则从图中某个顶点 i v 出发, 访问此顶点, 然后依次从 i v 的未被访问的邻接点