学时图的遍历ppt课件.ppt

《学时图的遍历ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法第14学时图的遍历图（graph）图是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继。它定义为G=(V，E)ABCDEABCDE0123401234无向图有向图无向图G=(V,E)顶点集V={A,B,C,D,E}边集E={(A,B),(A,C),(B,D),(C,D),(C,E),(D,E)}有向图G=(V,E)顶点集V={A,B,C,D,E}边集E={,,,,,}内容回顾：2图的存储结构-邻接矩阵

2、邻接矩阵顺序存储ABCDE内容回顾：主要内容：图遍历概念图的两种遍历(重点、难点）1.深度优先遍历2.广度优先遍历1.图遍历的概念从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。深度优先遍历(depth-firstsearch,DFS)广度优先遍历(breadth-firstsearch,BFS)V1V8V7V6V5V4V3V2V1V2V4V3V8V7V6V5深度遍历：V1,V2,V4,V5,V8,V3,V6,V

3、7V1V8V7V6V5V4V3V2V1V2V4V3V8V7V6V5深度遍历：V1,V3,V6,V7,V2,V5,V8,V4图的深度优先遍历（DFS）深度优先遍历(depth-firstsearch,DFS)1)任选图中某个未被访问的顶点v作为起点,访问v并标记为已访问;2)递归访问与v相邻且未被访问过的顶点.V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8深度遍历：V1V2V4V8V5V6V3V7深度遍历：V1V2V4V8V5V6V3V7课堂练习：7V1V

4、2V4V5V3V7V6V8深度遍历：V1V2V4V8V3V6V7V5深度遍历：V1V3V7V6V2V4V8V5课堂练习:8图的广度优先搜索（BFS）方法：类型于树的层次遍历（1）访问初始点v，接着访问v的所有未被访问过的邻接点v1，v2，…，vt。（2）按照v1，v2，…，vt的次序，访问每一个顶点的所有未被访问过的邻接点。（3）依次类推，直到图中所有和初始点v有路径相通的顶点都被访问过为止。9从图中某顶点v出发：1.访问顶点v2.访问v的所有未被访问的邻接点w1,w2,

5、…wk3.依次从这些邻接点出发，访问它们的所有未被访问的邻接点，直到图中所有访问过的顶点的邻接点都被访问到。V1V8V7V6V5V4V3V2V1V2V4V3V8V7V6V5广度优先遍历1:V1,V2,V3,V4,V8,V5,V6,V7广度优先遍历2:V1,V3,V2,V6,V7,V4,V5,V8图的广度遍历（BFS）V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V5V6V7V8课堂练习：

6、11V1V2V4V5V3V7V6V8例广度遍历：V1V2V3V4V5V6V7V8图的遍历（复习）深度遍历：V1V2V4V8V5V6V3V7当无向图是连通图、有向图是强连通图时，只需选一个起点，就能一次性遍历完图中所有顶点。12V1V2V4V5V3V7V6V8例广度遍历：V1V2V3V4V6V7V8图的广度优先搜索（BFS）注意：无向非连通图或有向非强连通图可能需要选择几个起点进行图的遍历。非连通图的遍历？V5第14页图的深度遍历（DFS）算法分析Vw1SG1

7、SG2SG3w2w3w2W1、W2和W3均为V的邻接点，SG1、SG2和SG3分别为含顶点W1、W2和W3的子图。访问顶点V：for(W1、W2、W3)若该邻接点W未被访问，则从它出发进行深度优先搜索遍历。第15页从图解可见：1.从深度优先搜索遍历连通图的过程类似于树的先根遍历；解决的办法是：为每个顶点设立一个“访问标志visited[w]”。2.如何判别V的邻接点是否被访问？Vw1SG1SG2SG3w2w3w2图的深度遍历（DFS）算法分析例如：abchdekfgFFFFFFFFFTTTTTTTT

8、Tachdkfebgachkfedbg访问标志:访问次序:012345678图的深度遍历（DFS）算法分析160273854图的深度优先遍历算法例G1bdac12341234acdbdatafirstarc3241^^^^adjvexnextarc深度遍历次序：a->c->d->b深度优先遍历需辅助数组，visited[0..n-1]，记录每个结点访问标志◆递归算法：//邻接表存储voidDFS(ALGraph*G，intv){ArcNode*p;intw;visit