第17讲图的遍历.ppt

EnQueue(Q, v); // v入队列 while ( !QueueEmpty(Q) ) { DeQueue(Q, u); // 队头元素出队为u并准备访问 Visited [u] = true ; Visit (u) ; //访问u for ( w=FirstAdjVex(G, u) ; w!=0; w=NextAdjVex(G,u,w) ) if ( ! visited[w]) { EnQueue(Q, w); // 下一个要访问的顶点w入队列 } // if } // while 算法分析 如果使用邻接表表示图，则循环的总时间代价为 d0 + d1 + … + dn-1 = O(e)，其中的 di 是顶点 i 的度。 如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的 n 个元素，总的时间代价为O(n2)。 三、遍历算法总结 1. 遍历图的过程实质上是通过边或弧找邻接点的过程，因此DFS和BFS的时间复杂度是相同的。 2. 对于一个图，它的DFS和BFS的有哪些信誉好的足球投注网站顺序不唯一，是由该图的存储结构决定的。 3、如果从无向图的任一顶点出发进行一次深度优先有哪些信誉好的足球投注网站即可访问所有顶点，则该图一定是连通图。 4、对于非连通图的遍历过程中每调用一次DFS算法都得到该图的一个连通分量。 数据结构 滨州学院计算机科学技术系 滨州学院计算机科学技术系 滨州学院计算机科学技术系 滨州学院计算机科学技术系 滨州学院计算机科学技术系 滨州学院计算机科学技术系 滨州学院计算机科学技术系 滨州学院计算机科学技术系 滨州学院计算机科学技术系 滨州学院计算机科学技术系 滨州学院计算机科学技术系 第七章 图 图的遍历 图的遍历 从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。 遇到的问题：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。 为避免重复访问，可设一个标志顶点是否被访问过的辅助数组 visited[],它的初始状态为0，在图遍历过程中，一旦某一个顶点i被访问，就修改 visited[i]为1，防止它被多次访问。 从图中某个顶点V0 出发，访问此顶点，然后选择一个与V0邻接且未被访问的顶点W为初始顶点，再从W出发进行深度优先有哪些信誉好的足球投注网站, 直至图中所有顶点都被访问到。 一、深度优先有哪些信誉好的足球投注网站遍历 连通图的深度优先有哪些信誉好的足球投注网站遍历 深度优先有哪些信誉好的足球投注网站DFS ( Depth First Search ) 深度优先有哪些信誉好的足球投注网站的示例 深度优先有哪些信誉好的足球投注网站过程 深度优先生成树 DFS 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问，… 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。 接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行有哪些信誉好的足球投注网站。重复上述过程，直到连通图中所有顶点都被访问过为止。 1. 深度优先有哪些信誉好的足球投注网站遍历连通图的过程类似于树的先根遍历； 为每个顶点设立一个 “访问标志 visited[w]”。 2. 如何判别V的邻接点是否被访问？ void DFSTraverse(Graph G, Status (*Visit)(int v) ) { // 对图 G 作深度优先遍历 VisitFunc = Visit； for (v=0; vG.vexnum; ++v) visited[v] = false; // 访问标志数组初始化 for (v=0; vG.vexnum; ++v) // 对尚未访问的顶点调用DFS if (!visited[v]) DFS(G, v); } Boolean visited[MAX]; Status (*VisitFunc)(int v); void DFS(Graph G, int v) { // 从第v个顶点出发，深度优先有哪些信誉好的足球投注网站遍历图 G visited[v] = true; VisitFunc(v); for(