图的基本概念及拓扑排序 (2).pptVIP

深度优先有哪些信誉好的足球投注网站(DFS)基本思想：——仿树的先序遍历过程。Depth_FirstSearchv1v1v2v3v8v7v6v4v5DFS结果例1：→→→→→→→v2v4v8v5v3v6v7例2：v2→v1→v3→v5→DFS结果v4→v6起点起点遍历步骤第30页，共53页，星期日，2025年，2月5日深度优先有哪些信誉好的足球投注网站（遍历）步骤：详细归纳：在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w1；再从w1出发，访问与w1邻接但还未被访问过的顶点w2；然后再从w2出发，进行类似的访问，…如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行有哪些信誉好的足球投注网站。重复上述过程，直到连通图中所有顶点都被访问过为止。简单归纳：访问起始点v;若v的第1个邻接点没访问过，深度遍历此邻接点；若当前邻接点已访问过，再找v的第2个邻接点重新遍历。第31页，共53页，星期日，2025年，2月5日基本算法新发现的结点先扩展得到的可能不是一棵树而是森林,即深度优先森林(Depth-firstforest)特别之处:引入时间戳(timestamp)发现时间d[v]:变灰的时间结束时间f[v]:变黑的时间1=d[v]f[v]=2|V|初始化:time为0,所有点为白色,dfs森林为空对每个白色点u执行一次DFS-VISIT(u)第32页，共53页，星期日，2025年，2月5日DFS-VISIT算法初始化:time为0,所有点为白色,dfs森林为空对每个白色点u执行一次DFS-VISIT(u)时间复杂度为O(n+m)第33页，共53页，星期日，2025年，2月5日第34页，共53页，星期日，2025年，2月5日DFS树的性质括号结构性质对于任意结点对(u,v),考虑区间[d[u],f[u]]和[d[v],f[v]],以下三个性质恰有一个成立:完全分离u的区间完全包含在v的区间内,则在dfs树上u是v的后代v的区间完全包含在u的区间内,则在dfs树上v是u的后代三个条件非常直观第35页，共53页，星期日，2025年，2月5日DFS树的性质定理1(嵌套区间定理):在DFS森林中v是u的后代当且仅当d[u]d[v]f[v]f[u],即区间包含关系.由区间性质立即得到.定理2(白色路径定理):在DFS森林中v是u的后代当且仅当在d[u]时刻(u刚刚被发现),v可以由u出发只经过白色结点到达.证明:由嵌套区间定理可以证明第36页，共53页，星期日，2025年，2月5日非递归形式的深度优先有哪些信誉好的足球投注网站算法voidDFS(GraphG,intv){//非递归算法InitStack(S);visited[]=FALSE;//所有的顶点尚未被访问过Push(S,v);//其实顶点压栈while(!Empty(S)){Pop(S,u);//访问顶点并修改标志数组if(!visited[u]){visit(u),visited[u]=TRUE};for(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w)){if(!visited[w])Push(G,w)}//将没访问的邻接点压栈}DestroyStack(S);//释放栈}//DFS第37页，共53页，星期日，2025年，2月5日数据结构书上的深度优先有哪些信誉好的足球投注网站算法boolvisited[max];//访问标志数组Status(*VisitFunc)(intv);//函数变量voidDESTraverse(GraphG,status(*visit)(intv)){//对图G进行深度优先有哪些信誉好的足球投注网站（图G连通与否都可以）visitFunc=visit;//使用全局变量Visitfunc，使DFS函数不必设置函数指针//访问标志数组初始化为全部没有访问for(v=0,vG.vecnum;++v)visitd[v]=false;for(v=0;vG.vexnu