图的遍历8.3图遍历的概念8.3.1从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图遍历。如果给定图是连通的无向图或者是强连通的有向图，则遍历一次就能完成，并可按访问的先后顺序得到由该图所有顶点组成的一个序列。1/84
从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方 法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这 个过程称为图遍历。 如果给定图是连通的无向图或者是强连通的有向图，则遍历一次就 能完成，并可按访问的先后顺序得到由该图所有顶点组成的一个序 列。 1/84
为了避免同一个顶点被重复访问，必须记住访问过的顶点。为此，可设置一个访问标志数组visited，初始时所有元素置为0，当顶点i访问过时，该数组元素visited[i]置为1。根据遍历方式的不同，图的遍历方法有两种：一种是深度优先遍历（DFS）方法：另一种是广度优先遍历（BFS）方法。DFS:01.4253BFS:012342/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
8.3.2深度优先遍历从图中某个起始点v出发进行深度优先搜索－DFS(v），首先访问初始顶点v。然后选择一个与顶点v邻接且没被访问过的顶点W为初始顶点，再从W出发进行深度优先搜索一DFS(W），直到图中与当前顶点v邻接的所有顶点都被访问过为止。递归过程3/84
从图中某个起始点v出发进行深度优先搜索— DFS(v) ，首先访问初始 顶点v。 然后选择一个与顶点v邻接且没被访问过的顶点w为初始顶点，再从w出 发进行深度优先搜索— DFS(w)，直到图中与当前顶点v邻接的所有顶 点都被访问过为止。 递归过程 3/84
图采用邻接表为存储结构，其深度优先遍历算法如下（其中，V是起始点编号visited是类成员数组）：publicstatic voidDFs(AdjGraphclass G,intv)int w;ArcNode p;1/访问顶点vSystem.out.print(v+"");1/置已访问标记visited[v]=1;//p指向顶点v的第一个邻接点p=G.adjlist[v].firstarc;while(p!=null)w=p.adjvex;if (visited[w]==0)1/若W顶点未访间，递归访问它DFS(G,W);1/p置为下一个邻接点p=p.nextarc;时间复杂度为o(n+e)。4/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(MatGraphclassg,int v)1/访问顶点V{ System.out.print(v+"");1/置已访问标记visited[v]=1;for (int w=o;w并且w没有访问过(if (visited[w]==o)DFS(g,w);若W顶点未访问，递归访问它时间复杂度为0(n2)。5/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
DFS:015 23 46/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
理解深度优先遍历过程7/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
起始点到图中其他顶点的路径长度：DFS:0152344→3说明类似树的先根遍历。8/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
8.3.3广度优先遍历首先访问起始点V。接着访问顶点v的所有未被访问过的邻接点V1、V2、…、Vt。然后再按照v1、V2、…、Vt的次序，访问每一个顶点的所有未被访问过的邻接点。依次类推，直到图中所有和初始点v有路径相通的顶点或者图中所有已访问顶点的邻接点都被访问过为止。队列相邻顶点：先访问先处理9/84
首先访问起始点v。 接着访问顶点v的所有未被访问过的邻接点v1、v2、.、vt。 然后再按照v1、v2、.、vt的次序，访问每一个顶点的所有未被访问 过的邻接点。 依次类推，直到图中所有和初始点v有路径相通的顶点或者图中所有已 访问顶点的邻接点都被访问过为止。 相邻顶点：先访问先处理 9/84
图采用邻接表为存储结构，其广度优先遍历算法如下：public static void BFs(AdjGraphclass G,int vArcNode p; int w;//定义一个队列Queuequ=newLinkedList();1/访问顶点VSystem.out.print(v+"");1/置已访问标记visited[v]-1;1/v进队qu.offer(v);while(!qu.isEmpty())1/队列不空循环//出队顶点Vv=qu.pol1();//找顶点v的第一个邻接点p=G.adjlist[v].firstarc;while (p!=null) w=p.adjvex;1/若v的邻接点w未访问if(visited[w]==0)1/访问顶点w{System.out.print(w+"");1/置已访标记visited[w]=1;1 /w进队qu.offer(w);1/找下一个邻接顶点p=p.nextarc;10/84时间复杂度为o（n+e）
图采用邻接表为存储结构，其广度优先遍历算法如下： 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