84图的遍历 遍历定义:从已给的连通图中某一顶点出发,沿着一些边,访 遍图中所有的顶点,且使每个顶点仅被访问一次,就叫做 图的遍历,它是图的 遍历实质:找每个顶点的邻接点的过程。 图的特点:图中可能存在,且图的任一顶点都可能与其它 顶点相通,在访问完某个顶点之后可能会沿着某些边又回 到了曾经访问过的顶点。 怎样避免重复访问? 解决思路:可设置一个辅助数组 visited n],用来标记每个被 访问过的顶点。它的初始状态为0,在图的遍历过程中 旦某一个顶点被访问,就立即改 visited[为1,防止它 被多次访向问。 深度优先搜索 图常用的遍历: 、广度优先搜索
1 一、深度优先搜索 二、广度优先搜索 8.4 图的遍历 遍历定义：从已给的连通图中某一顶点出发，沿着一些边，访 遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做 图的遍历，它是图的基本运算。 遍历实质：找每个顶点的邻接点的过程。 图的特点：图中可能存在回路，且图的任一顶点都可能与其它 顶点相通，在访问完某个顶点之后可能会沿着某些边又回 到了曾经访问过的顶点。 解决思路：可设置一个辅助数组 visited [n ]，用来标记每个被 访问过的顶点。它的初始状态为0，在图的遍历过程中， 一旦某一个顶点i被访问，就立即改 visited [i]为1，防止它 被多次访问。 图常用的遍历： 怎样避免重复访问？
深度优先搜索(DFS) Depth First Search 基本思想:仿树的先序遍历过程 例1:人 DFS结果 v1→v2→→v4-v8 V5→V3-V6→V7 v0八 记 例2: DFS结果 12→v1→V3→V5 V4→V6
2 一、深度优先搜索( DFS ) 基本思想：——仿树的先序遍历过程。 Depth_First Search v1 v1 v2 v3 v8 v6 v7 v4 v5 例1： DFS 结果 → → → → → → → v2 v4 v8 v5 v3 v6 v7 例2： v2 → v1 → v3 → v5 → DFS 结果 v4 → v6 起点 起点 应退回到V8，因为V2已有标 记
深度优先搜索(遍历)步骤 简单归纳: 访问起始点 若v的第1个邹接点没访问过,深度遍历此邻接点; 若当前邻接点已访问过,再找v的第2个邻接点重新遍历。 详细归纳: 在访问图中某一起始顶点ν后,由ν出发,访问它的任一邻接 顶点w1; 再从w出发,访问与w1邻接但还未被访问过的顶点w 然后再从w2出发,进行类似的访问, 如此进行下去,直至到达所有的邻接顶点都被访问过的顶点u 为止 接着,退回一步,退到前一次刚访问过的顶点,看是否还有其 它未被访问的邻接顶点。 则访问此顶点,之后再从此顶点出发,进行与前述 类似的访问 就再退回一步进行搜索。重复上述过程,直到连 通图中所有顶点都被访问过为止
3 深度优先搜索（遍历）步骤： 详细归纳： 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接 顶点 w1； 再从 w1 出发，访问与 w1邻接但还未被访问过的顶点 w2； 然后再从 w2 出发，进行类似的访问，… 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。 接着，退回一步，退到前一次刚访问过的顶点，看是否还有其 它未被访问的邻接顶点。 如果有，则访问此顶点，之后再从此顶点出发，进行与前述 类似的访问； 如果没有，就再退回一步进行搜索。重复上述过程，直到连 通图中所有顶点都被访问过为止。 简单归纳： • 访问起始点v; • 若v的第1个邻接点没访问过，深度遍历此邻接点； • 若当前邻接点已访问过，再找v的第2个邻接点重新遍历
二、广度优先搜索(BFS) Breadth First Search 基本思想:仿树的层次遍历过程 例1 BFS结果 v1→v2→V3 V4y56-v7v8 起点 BFS结果 层 V3→V2→V1→V6 V4→V5-9→v8→v7 二层 三层
4 二、广度优先搜索( BFS ) 基本思想：——仿树的层次遍历过程。 Breadth_First Search v1 v1 v2 v3 v8 v6 v7 v4 v5 例1： BFS 结果 → → → v2→v3 v4→v5 v6→v7→v8 例2： v3 → BFS 结果 v4 → v5 → 起点 起点 v2 → v1 → v6 → v9 → v8 → v7
广度优先搜索(遍历)步骤: 简单归纳: 在访问了起始点v之后,依次访问v的邻接点; 然后再依次(顺序)访问这些点(下一层)中未被 访问过的邻接点; 直到所有顶点都被访问过为止
5 广度优先搜索（遍历）步骤： 简单归纳： • 在访问了起始点v之后，依次访问 v的邻接点； • 然后再依次（顺序）访问这些点（下一层）中未被 访问过的邻接点； • 直到所有顶点都被访问过为止。 广度优先搜索是一种分层的搜索过程，每向前走一 步可能访问一批顶点，不像深度优先搜索那样有回 退的情况。 因此，广度优先搜索不是一个递归的过程，其算法 也不是递归的