深度优先搜索课件.ppt

《深度优先搜索课件.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