(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出发按深度优先有哪些信誉好的足球投注网站法进行遍历，则得到的一种顶点序列为：