文档介绍：第7章图图是一种多对多的结构关系,每个元素可以有零个或多个直接前趋;零个或多个直接后继。.2020/8/51【重点掌握】:图的两种遍历方法:遍历的定义、深度优先搜索遍历和广度优先搜索遍历的算法;应用图的遍历算法判断图的连通性及求图的生成树;用Prim、算法求图的最小生成树;用算法求解单源最短路径问题;用Floyd算法求所有顶点间的最短路径问题;利用AOV网进行拓扑排序;利用AOE网求关键路径问题;【掌握】:掌握图的定义和术语;图的各种存储结构及其构造算法、在实际问题中的求解效率。.27.3图的遍历7.3图的遍历:从图的某顶点出发,访问图中所有顶点,并且每个顶点仅访问一次。图结构的遍历复杂性:(1)在图结构中,没有一个“自然”的首结点,图中的任意一个顶点都可以作为第一个被访问的结点(2)在非连通图中,从一个顶点出发,只能访问它所在的连通分量上的所有顶点,因此,还需考虑如何选取下一个出发点以访问图中的其余连通分量(3)在图结构中,如果有回路存在,那么一个顶点被访问后,有可能沿回路又回到该顶点,考虑如何避免重复访问(4)在图结构中,一个顶点可以和其他多个顶点邻接,当这样的顶点访问过后,考虑如何选取下一个要访问的顶点的问题.3图的遍历方法有深度优先遍历和广度优先遍历两种。
7.3.1深度优先搜索方法:(1)从图的某一顶点V0出发数据结构最短路径ppt-数据结构 第七章-图ppt课件.ppt,访问此顶点;(2)依次从V0的未被访问的邻接点出发,深度优先遍历图,直至图中所有和V0相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未被访问的顶点作起点,重复上述过程,直至图中所有顶点都被访问到。.若图的存储结构为邻接表,则访问邻接点的顺序不唯一,深度优先序列不是唯一的,V1,V3,V4,V7,V2,V5,V6,※求图G以V0为起点的的深度优先序列(设存储结构为邻接矩阵).(,intv){/从第v个顶点出发,递归地深度优先遍历图G//v是顶点在一维数组中的位置,假设G是非空图/[v]=1;Visit(v);/访问第v个顶点/for(w=(G,v);w;w=(G,v,w))if(![w])DFS(G数据结构最短路径ppt,w);/对v的尚未访问的邻接顶点w递归调用DFS/}辅助数组:[];访问标志数组数据结构最短路径ppt,全局变量,初始时所有分量全为0,[v]=1表示顶点v已被访问.……00000深度优先遍历算法:7.3图的遍历.67.3图的遍历在邻接表存储结构上实现深度优先搜索:()/深度优先遍历以邻接表存储的图G/{inti;for(i=0;){w=p->;/w是v的邻接顶点的序号/if(![w])DFSAL(G,w);/若w尚未访问,递归调用DFS/}}/DFSAL/7.3图的遍历.8在遍历时,对图中每个顶点至多调用一次DFS函数,因为一旦某个顶点被标志成已被访问,就不再从它出发进行搜索。
因此,遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。用邻接矩阵做图的存储结构时,查找各个顶点的邻接点所需的时间为O(n2),其中n为图中顶点数。当以邻接矩阵做存储结构时,深度优先搜索遍历图的时间复杂度为O(n2+n)。当以邻接表做图的存储结构时,找邻接点所需时间为O(e),其中e为无向图中边的数或有向图中弧的数。因此,当以邻接表做存储结构时,深度优先搜索遍历图的时间复杂度为O(n+e)。7.3图的遍历.9图中某顶点v出发:1)访问顶点v;2)访问v的所有未被访问的邻接点w1,w2,…wk;3)依次从这些邻接点出发,访问它们的所有未被访问的邻接点;依此类推,直到图中所有访问过的顶点的邻接点都被访问;7.3.2广度优先遍历7.3图的遍历.10