知识点13：图的遍历PPT课件

1、知识点知识点13：图的遍历：图的遍历1、图的遍历通常有深度优先搜索和广度优先搜索两种方式。深度优先搜索是一个递、图的遍历通常有深度优先搜索和广度优先搜索两种方式。深度优先搜索是一个递归的过程，而广度优先搜索是一个非递归过程。归的过程，而广度优先搜索是一个非递归过程。（1）深度优先搜索）深度优先搜索递归算法递归算法非递归算法非递归算法图的存储结构用邻接矩阵表示时，深度优先搜索遍历图的时间复杂度为图的存储结构用邻接矩阵表示时，深度优先搜索遍历图的时间复杂度为O(n2) 。当以。当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e)

2、。深度优先搜。深度优先搜索遍历图的空间复杂度为索遍历图的空间复杂度为O(n)。（2）广度优先搜索：广度优先搜索遍历图的时间复杂度和深度优先搜索遍历的）广度优先搜索：广度优先搜索遍历图的时间复杂度和深度优先搜索遍历的相同，两者不同之处仅仅在于对顶点访问的顺序不同。相同，两者不同之处仅仅在于对顶点访问的顺序不同。2、树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索、树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略策略。题题1如果从无向图的任一顶点出发进行一次深度优先搜素即可访问所有顶点，则该图如果从无向图的任一顶点出发进行一次深度优先搜素即可访问所有顶点，则

3、该图一定是（一定是（ ）。）。A.完全图完全图 B.连通图连通图 C.有回路有回路 D.一棵树一棵树分析：对于无向图来说，若无向图是连通图，则一次遍历能够访问到图中的所有顶点，分析：对于无向图来说，若无向图是连通图，则一次遍历能够访问到图中的所有顶点，但若无向图是非连通图，则只能访问到初始点所在连通分量中的所有顶点，其他连但若无向图是非连通图，则只能访问到初始点所在连通分量中的所有顶点，其他连通分量中的顶点不可能访问到。通分量中的顶点不可能访问到。解答：解答：B。题题2 假设图假设图G采用邻接表存储，设计一个算法，输出图采用邻接表存储，设计一个算法，输出图G中从顶点中从顶点u到到v的长度为的长

4、度为k的所有简单路径。的所有简单路径。分析：所谓简单路径是指路径上的顶点不重复。本题利用回溯的深度优先搜索方分析：所谓简单路径是指路径上的顶点不重复。本题利用回溯的深度优先搜索方法，从顶点法，从顶点u开始，进行深度优先搜索。由于在搜索过程中，每个顶点只访问一开始，进行深度优先搜索。由于在搜索过程中，每个顶点只访问一次且不重复访问，所以这条路径必定是一条简单路径。因此，在搜索过程中，需次且不重复访问，所以这条路径必定是一条简单路径。因此，在搜索过程中，需要把当前的搜索线路记录下来。为了记录当前的搜索路径，可设立一个数组要把当前的搜索线路记录下来。为了记录当前的搜索路径，可设立一个数组path保存

5、走过的路径，用保存走过的路径，用d记录走过的路径长度。若当前扫描到的结点记录走过的路径长度。若当前扫描到的结点u等于等于v且路径且路径长度为长度为k时，表示找到了一条路径，则输出路径时，表示找到了一条路径，则输出路径path。void PathAll(ALGraph *G,int u,int v,int k,int path,int d)/d是到当前已走过的路径长度，调用时初值为是到当前已走过的路径长度，调用时初值为-1 int m,i; ArcNode *p; visitedu=1; d+; /路径长度加路径长度加1 pathd=u; /将当前顶点添加到路径中将当前顶点添加到路径中 if (u= =v & d= =k) for (i=0;iadjlistu.firstarc; /p指向顶点指向顶点u的第一条弧的弧头结点的第一条弧的弧头结点 while (p!=NULL) m=p-adjvex; /m为为u的邻接顶点的邻接顶点 if (visitedm= =0) PathAll(G,m,v,k,path,d); /若该顶点未标记访问，则用递归访问它若该顶点未标记访问，则用递归访问它 p-nextar