图的遍历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<g.n;w++)(if (g.edges[v][w]!=0 &&g.edges[v][w]!=g.INF)/ /存在边<V,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<g.n;w++) { if (g.edges[v][w]!=0 &&g.edges[v][w]!=g.INF) { if (visited[w]==0) //存在边<v,w>并且w没有访问过 DFS(g,w); //若w顶点未访问,递归访问它 } } } 时间复杂度为O(n 2)。 5/84