河池学院：《数据结构》课程电子教案（PPT教学课件）第8章 图 8.3 图的遍历

从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方 法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这 个过程称为图遍历。 如果给定图是连通的无向图或者是强连通的有向图，则遍历一次就 能完成，并可按访问的先后顺序得到由该图所有顶点组成的一个序 列。 1/84

为了避免同一个顶点被重复访问，必须记住访问过的顶点。为此，可设 置一个访问标志数组visited，初始时所有元素置为0，当顶点i访问过 时，该数组元素visited[i]置为1。 根据遍历方式的不同，图的遍历方法有两种：一种是深度优先遍历 （DFS）方法；另一种是广度优先遍历（BFS）方法。 0 1 2 3 4 5 DFS: 0 1 4 2 5 3 BFS: 0 1 2 3 4 5 2/84

从图中某个起始点v出发进行深度优先搜索— DFS(v) ，首先访问初始 顶点v。 然后选择一个与顶点v邻接且没被访问过的顶点w为初始顶点，再从w出 发进行深度优先搜索— DFS(w)，直到图中与当前顶点v邻接的所有顶 点都被访问过为止。 递归过程 3/84

图采用邻接表为存储结构，其深度优先遍历算法如下（其中，v是起始点编号， visited是类成员数组）： public static void DFS(AdjGraphClass G,int v) { int w; ArcNode p; System.out.print(v+" "); //访问顶点v visited[v]=1; //置已访问标记 p=G.adjlist[v].firstarc; //p指向顶点v的第一个邻接点 while (p!=null) { w=p.adjvex; if (visited[w]==0) DFS(G,w); //若w顶点未访问,递归访问它 p=p.nextarc; //p置为下一个邻接点 } } 时间复杂度为O(n+e)。 4/84

图采用邻接矩阵为存储结构，其深度优先遍历算法如下（其中，v是起始点编 号，visited是类成员数组）： public static void DFS(MatGraphClass g,int v) { System.out.print(v+" "); //访问顶点v visited[v]=1; //置已访问标记 for (int w=0;w并且w没有访问过 DFS(g,w); //若w顶点未访问,递归访问它 } } } 时间复杂度为O(n 2)。 5/84

1 4 0 2 3 5 1 4 0 2 3 5 0 v0 1 1 v1 5 ∧ 2 v2 3 3 v3 ∧ 2 ∧ 4 5 ∧ 5 v5 ∧ 4 v4 3 ∧ DFS: 0 1 5 2 3 4 6/84

14 0 2 35 0 v 0 1 1 v 1 5 ∧ 2 v 2 3 3 v 3 ∧ 2 ∧ 4 5 ∧ 5 v 5 ∧ 4 v 4 3 ∧ 1 3 0 2 5 4 7/84

0 0 → 1 0 → 1 → 5 0 → 2 0 → 2 → 5 0 → 2 → 3 0 → 2 → 4 0 → 2 → 4 → 3 起始点0到图中其他顶点的路径长度： DFS: 0 1 5 2 3 4 说明 类似树的先根遍历。 1 3 0 2 5 4 8/84

首先访问起始点v。 接着访问顶点v的所有未被访问过的邻接点v1、v2、.、vt。 然后再按照v1、v2、.、vt的次序，访问每一个顶点的所有未被访问 过的邻接点。 依次类推，直到图中所有和初始点v有路径相通的顶点或者图中所有已 访问顶点的邻接点都被访问过为止。 相邻顶点：先访问先处理 9/84

图采用邻接表为存储结构，其广度优先遍历算法如下： public static void BFS(AdjGraphClass G,int v) { ArcNode p; int w; Queue qu=new LinkedList(); //定义一个队列 System.out.print(v+" "); //访问顶点v visited[v]=1; //置已访问标记 qu.offer(v); //v进队 while (!qu.isEmpty()) //队列不空循环 { v=qu.poll(); //出队顶点v p=G.adjlist[v].firstarc; //找顶点v的第一个邻接点 while (p!=null) { w=p.adjvex; if (visited[w]==0) //若v的邻接点w未访问 { System.out.print(w+" "); //访问顶点w visited[w]=1; //置已访问标记 qu.offer(w); //w进队 } p=p.nextarc; //找下一个邻接顶点 } } } 时间复杂度为O(n+e)。 10/84