数据结构,图的遍历.ppt

图的遍历 从图的任一顶点出发，沿着边访遍图中所有顶点，且每个顶点仅访问一次，这一过程称作图的遍历 ( Graph Traversal )。 图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历的基础之上。 分析 出发结点：在图结构中，没有一个“自然”的首结点 。用户指定。 图的连通性：非连通图中，从一个顶点出发，只能访问它所在的连通分量上的所有顶点。用户指定下一个出发点访问其它连通分量。 重复访问：访问完某个顶点后可能沿着某些边又回到曾经访问过的顶点。避免重复，用标识数组visited[ ]。初值为0，标识未访问。如果顶点 i 被访问，则置visited[i]为1. 访问策略：多个邻接顶点，如何选择下一个访问顶点。 1. 深度优先遍历 深度优先遍历又被称为深度优先有哪些信誉好的足球投注网站 ( Depth First Search， DFS ) 访问策略: 从图中某一起始顶点 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻接但还没有访问过的任一顶点 w2；… 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点。此时，回溯到上一个被访问的顶点，看它是否还有其它没被访问的邻接顶点。若有，则访问该邻接顶点，进行与前述类似的访问；若没有，进一步回溯。 递归算法描述 算法DepthFirstSearch (v) /* 图的深度优先遍历的递归算法,标识数组visited全局*/ D1[初始化] cout v; visited[v] = 1; D2[深度优先遍历] for( p = Head[v] - adjacent ; p ; p = p - link ) if (visited[ p - VerAdj ] != 1 ) 　　 　　DepthFirstSearch (p - VerAdj);? DFS算法分析 如果用邻接表表示图，沿顶点的adjacent可以找到某个顶点v 的所有邻接顶点w。DFS每个结点只访问一次，由于总共有2e 个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。 如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2)。 迭代算法 将visited[]值置为0, 初始顶点压入栈； 检测栈是否为空。若堆栈为空，则迭代结束； 否则，从栈顶弹出一个顶点v；如果v未被访问过，则访问v，将visited[v]值更新为1，然后根据v的邻接顶点表，将v的未被访问的邻接顶点压入栈，转到步骤2。 迭代算法DFS (v) /* 用栈 S非递归深度优先遍历图 G, G采用邻接表存储, 标识数组visited[]*/ DFS1. [初始化] for( i=1 ; i=n ; i++ ) visited[i] = 0； CREATSTACK S ； S.push(v). DFS2. [用S 深度优先遍历] while ( ! S.empty()){ v = S.pop(); coutv; visited[v]=1; for( p=Head[v]-adjacent ；p ; p = p - link ） if(visited [ p -VerAdj] ==0 ) S.push( p-VerAdj); }? 非连通图的处理 多次调用深度优先遍历算法 for ( i=1; i=n; i++ ) visited[i] = 0; for ( i=1; i=n; i++ ) if ( visited[j] == 0 ) DepthFirstSearch ( i) 2. 广度优先遍历 广度优先遍历又称为广度优先有哪些信誉好的足球投注网站 (Breadth First Search, BFS ) 访问策略：首先访问初始点顶点v0，之后依次访问与v0邻接的全部顶点w1，w2，...，wk。然后，再顺次访问与w1，w2，...，wk邻接的尚未访问的全部顶点，再从这些被访问过的顶点出发，逐个访问与它们邻接的尚未访问过的全部顶点。依此类推，直到连通图中的所有顶点全部访问完为止。 广度优先有哪些信誉好的足球投注网站是一种分层的有哪些信誉好的足球投注网站过程，每向前走一步可能访问一批顶点，不像深度优先有哪些信誉好的足球投注网站那样有回退的情况。 为了实现逐层访问，算法中使用一个队列，以便于向下一层访问。 算法BFS (v) /*广度优先遍历算法 */ BFS1[初始化] for ( i =1 ; i = n ; i++ ) visited[i] = 0; CREATQ