资源描述:
《深度优先搜索课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、SevenBridgesofKönigsberg(柯尼斯堡)第七章图7.1图的定义和基本术语7.2图的存储7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径第七章图7.1图的定义和基本术语7.2图的存储7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径第七章图回顾:图的存储结构邻接矩阵表示法(Adjacencymatrix)邻接表表示法(Adjacencylist)0101101101001100edges=ABCDABCD邻接矩阵表示法ADBC邻接表表示
2、法0A1B2C3D^120^303^02^ADBC7.1图的定义和基本术语7.2图的存储7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径第七章图什么是图的遍历?从图中某一顶点出发访遍图中其余顶点,且使每个顶点仅被访问一次,这一过程就叫做图的遍历。根据遍历路径的不同,通常有两种遍历方法:深度优先搜索广度优先搜索图的遍历与树的遍历的区别?ADBC假定从某顶点出发,采用树的遍历方法,沿着某条路径搜索后,可能又回到该顶点。原因:图中可能存在回路。图的遍历与树的遍历的区别?ADBC解决
3、办法:采用一个辅助数组visited[0…n-1]用于记录已访问的结点。visited[i]=0→未被访问visited[i]=1→已访问类似于树的先序遍历(使用堆栈)遍历过程假设初始状态图中顶点均未被访问,从顶点v出发访问该顶点;依次从v的未被访问的邻接点出发深度优先遍历,直到与v有路径相通的所有顶点都被访问到;若图中尚有顶点未被访问到,则选择其中一个顶点作为新的起始点,重复(1)(2)步骤直到图中所有顶点都访问完毕。7.3.1深度优先搜索无向图的深度优先搜索邻接表:A:CEB:CDC:ABD
4、D:BCE:AF:GG:FCAEBDFG未遍历已标记当前访问点输出:visit(A)(A,C)(A,E)未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表:A:CEB:CDC:ABDD:BCE:AF:GG:FCAEBDFG输出:Avisit(A)(A,C)(A,E)未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表:A:CEB:CDC:ABDD:BCE:AF:GG:FCAEBDFGvisit(C)(C,A)(C,B)(C,D)输出:ACvisit(A)(A,C)(A,E
5、)未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表:A:CEB:CDC:ABDD:BCE:AF:GG:FCAEBDFGvisit(C)(C,A)(C,B)(C,D)输出:ACvisit(A)(A,C)(A,E)未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表:A:CEB:CDC:ABDD:BCE:AF:GG:FCAEBDFGvisit(C)(C,A)(C,B)(C,D)visit(B)(B,C)(B,D)输出:ACBvisit(A)(A,C)(A,E)未遍历已标记当前访问
6、点堆栈无向图的深度优先搜索邻接表:A:CEB:CDC:ABDD:BCE:AF:GG:FFGvisit(C)(C,A)(C,B)(C,D)visit(B)(B,C)(B,D)CAEBD输出:ACBvisit(A)(A,C)(A,E)未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表:A:CEB:CDC:ABDD:BCE:AF:GG:FFGvisit(C)(C,A)(C,B)(C,D)visit(B)(B,C)(B,D)visit(D)(D,B)(D,C)CAEBD输出:ACBDv
7、isit(A)(A,C)(A,E)未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表:A:CEB:CDC:ABDD:BCE:AF:GG:FFGvisit(C)(C,A)(C,B)(C,D)visit(B)(B,C)(B,D)visit(D)(D,B)(D,C)CAEBD输出:ACBDvisit(A)(A,C)(A,E)未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表:A:CEB:CDC:ABDD:BCE:AF:GG:FFGvisit(C)(C,A)(C,B)(C,D)vis
8、it(B)(B,C)(B,D)visit(D)(D,B)(D,C)CAEBD输出:ACBDvisit(A)(A,C)(A,E)未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表:A:CEB:CDC:ABDD:BCE:AF:GG:FFGvisit(C)(C,A)(C,B)(C,D)visit(B)(B,C)(B,D)CAEBD输出:ACBDvisit(A)(A,C)(A,E)未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表:A:CEB:CDC:ABD