学时图的遍历ppt课件.ppt

数据结构与算法第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={<A,C>,<B,A>,<B,D>,<C,D>,<D,E>,<E,C>}内容回顾:2图的存储结构-邻接矩阵邻接矩阵顺序存储ABCDE内容回顾:主要内容:图遍历概念图的两种遍历(重点、难点)从给定图中任意指定的顶点(称为初始点)出发,按照某种搜索方法沿着图的边访问图中的所有顶点,使每个顶点仅被访问一次,这个过程称为图的遍历。深度优先遍历(depth-firstsearch,DFS)广度优先遍历(breadth-firstsearch,BFS)V1V8V7V6V5V4V3V2V1V2V4V3V8V7V6V5深度遍历:V1,V2,V4,V5,V8,V3,V6,V7V1V8V7V6V5V4V3V2V1V2V4V3V8V7V6V5深度遍历:V1,V3,V6,V7,V2,V5,V8,V4图的深度优先遍历(DFS)深度优先遍历(depth-firstsearch,DFS)1)任选图中某个未被访问的顶点v作为起点,访问v并标记为已访问;2):V1V2V4V8V5V6V3V7深度遍历:V1V2V4V8V5V6V3V7课堂练习:7V1V2V4V5V3V7V6V8深度遍历: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出发: ,w2,…wk ,访问它们的所有未被访问的邻接点,直到图中所有访问过的顶点的邻接点都被访问到。V1V8V7V6V5V4V3V2V1V2V4V3V8V7V6V5广度优先遍历1:V1,V2,V3,V4,V8,V5,V6,V7广度优先遍历2:V1,V3,V2,V6,V7,V4,V5,V8图的广度遍历(BFS)