深度优先搜索

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)7.1图的定义和基本术语7.2图的存储7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径第七章图什么是图的遍历？从图中某一顶点出发访遍图中其余顶点，且使每个顶点仅被访问一次，这一过程就叫做图的遍历。根据遍历路径的不同，通常有两种遍历方法：深度优先搜索广度优先搜索类似于树的先序遍历（使用堆栈）遍历过程(1)假设初始状态图中顶点均未被访问，从顶点v出发访问该顶点；(2)依次从v的未被访问的邻接点出发深度优先遍历，直到与v有路径相通的所有顶点都被访问到；(3)若图中尚有顶点未被访问到，则选择其中一个顶点作为新的起始点，重复(1)(2)步骤直到图中所有顶点都访问完毕。7.3.1深度优先搜索无向图的深度优先搜索邻接表：A:CEB:CDC:ABDD: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)未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表：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)未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表：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输出：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)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)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:ABDD:BCE:AF:GG:FFGvisit(C)(C,A)(C,B)(C,D)CAEBD输出：ACBDvisit(A)(A,C)(A,E)未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表：A:CEB:CDC:ABDD:BCE:AF:GG:FFGvisit(C)(C,A)(C,B)(C,D)CAEBD输出：ACBDvisit(A)(A,C)(A,E)未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表：A:CEB:CDC:ABDD:BCE:AF:GG:FFGCAEBD输出：ACBDvisit(A)(A,C)(A,E)未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表：A:CEB:CDC:ABDD:BCE:AF:GG:FFGCAEBDvisit(E)(E,A)输出：ACBDEvisit(A)(A,C)(A,E)未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表：A:CEB:CDC:ABDD:BCE:AF:GG:FFGCAEBDvisit(E)(E,A)输出：ACBDEvisit(A)(A,C)(A,E)未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表：A:CEB:CDC:ABDD:BCE:AF:GG:FFGCAEBD输出：ACBDE未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表：A:CEB:CDC:ABDD:BCE:AF:GG:FFGCAEBD输出：ACBDE未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表：A:CEB:CDC:ABDD:BCE:AF:GG:FFGvisit(F)(F,G)CAEBD输出：ACBDEF未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表：A:CEB:CDC:ABDD:BCE:AF:GG:FFGvisit(F)(F,G)visit(G)(G,F)CAEBD输出：ACBDEFG未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表：A:CEB:CDC:ABDD:BCE:AF:GG:Fvisit(F)(F,G)visit(G)(G,F)CAEBDFG输出：ACBDEFG未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表：A:CEB:CDC:ABDD:BCE:AF:GG:Fvisit(F)(F,G)CAEBDFG输出：ACBDEFG未遍历已标记当前访问点堆栈无向图的深度优先搜索邻接表：A:CEB:CDC:ABDD:BCE:AF:GG:FCAEBDFG输出：ACBDEFG深度优先搜索算法voidDFSTraverse(GraphG){for(v=0;vG.vexnum;v++)visited[v]=0;for(v=0;vG.vexnum;v++)if(!visited[v])DFS(G,v);}voidDFS(GraphG,intv){visited[v]=1;Visit(v);for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);}深度优先搜索算法时间复杂度(1)采用邻接矩阵：O(n2)(2)采用邻接表：O(n+e)深度优先搜索法的应用求非连通图中的连通分量的个数；寻找欧拉回路(Eulertour)的遍历路径。作业设在A、B、C、D四地之间架设有6座桥，要求从某一地出发，经过每座桥恰巧一次，最后返回原地。（1）此问题有解的条件是什么？（2）设图中的顶点数为n，试用C语言描述与求解此问题有关的数据结构并编写算法，找出满足要求的一条回路。ABCD