(14)--第5章-图的遍历数据结构.ppt

第6章图图的遍历

图的遍历深度优先搜索的过程和算法广度优先搜索的过程和算法123内容安排

1.什么是图的遍历？从初始点出发，按照某种搜索方法沿着图的边访问图中所有顶点，仅访问一次。BDACECEDACDAE

图的遍历方法避免重复访问1.1图的遍历要解决的关键问题深度优先搜索广度优先搜索数组visited[]

GFBADEC2.深度优先搜索过程

（DFS——DepthFirstSearch）访问初始顶点v。选取w∈{v未被访问的邻接点}，从w出发进行DFS；重复前两步……DCABEv=C的DFS序列：CBADEFGFG仿树的先序遍历

2.1深度优先搜索过程详细归纳在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w1；再从w1出发，访问与w1邻接但还未被访问过的顶点w2；然后再从w2出发，进行类似的访问，…如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

2.2深度优先搜索算法voidDFS(VertexV){visited[V]=1;for(V的每个邻接点W)if(!visited[W])DFS(W);}递归函数

2.3DFS函数执行过程DFS（A）ADFS（B）DFS（E）BECACDBEDFS（C）DFS（D）DBCDE

讨论1：计算机如何实现DFS？123456100000020000003000000400000050000006000000000000123456010000110000111000111010111110111111DFS结果邻接矩阵A辅助数组visited[n]1234561011100210001031000104100001501100060001002134562→1→3→5→4→6

voidDFS(AMGraphG,intv){//图G为邻接矩阵类型coutv;visited[v]=true; //访问第v个顶点for(w=0;wG.vexnum;w++)//依次检查邻接矩阵v所在的行if((G.arcs[v][w]!=0)(!visited[w]))DFS(G,w);//w是v的邻接点，如果w未访问，则递归调用DFS}讨论2：在图的邻接矩阵中DFS算法如何编程？

讨论3：在图的邻接表中如何进行DFS？v0→v1→v2→v3DFS结助数组visited[n]1000110011101111—照样借用visited[n]起点0123

2024年3月11日北京林业大学信息学院讨论4：邻接表的DFS算法如何编程？voidDFS(ALGraphG,intv){ //图G为邻接表类型coutv;visited[v]=true; //访问第v个顶点p=G.vertices[v].firstarc;//p指向v的边链表的第一个边结点while(p!=NULL){ //边结点非空w=p-adjvex; //表示w是v的邻接点if(!visited[w])DFS(G,w); //如果w未访问，则递归调用DFSp=p-nextarc; //p指向下一个边结点}}

2.4DFS算法效率分析用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O(n2)。用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为O(n+e)。结论：稠密图适于在邻接矩阵上进行深度遍历；稀疏图适于在邻接表上进行深度遍历。

给定无向图G，从V0出发进行深度优先遍历访问的边集合为：{(V0,V1),(V0,V4),(V1,V2),(V1,V3),(V4,V5),(V5,V6)}。则下面哪条边不可能出现在G中？(V0,V2)(V0,V6)(V1,V5)(V4,V6)ABCD提交单选题2分

给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历，则得到的一种顶点序列为：