图的遍历与连通性.ppt

第7章 图 7.3 图的遍历 一、深度优先有哪些信誉好的足球投注网站( DFS ) DFS 算法效率分析: 二、广度优先有哪些信誉好的足球投注网站( BFS ) BFS 算法效率分析: 例1 ：画出下图的生成树。 例2：画出下图的生成森林（或极小连通子图） 2. 求无向网的最小生成树 * 7.1 基本术语 7.2 存储结构 7.3 图的遍历 7.4 图的连通性 7.5 图的应用 遍历：从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。 遍历实质：找每个顶点的邻接点的过程。 图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。 解决思路：可设置一个辅助数组 visited [n ]，用来标记每个被访问过的顶点。它的初始状态为false，在图的遍历过程中，一旦某一个顶点i 被访问，就立即改 visited [i]为true，防止它被重复访问。 怎样避免重复访问？ 深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站 图常用的遍历： Depth_First Search 基本思想：——类似于树的先根遍历过程。 1、连通图的深度优先有哪些信誉好的足球投注网站遍历 步骤： 访问起始点 v; 依次从v的未被访问的邻接点出发深度优先遍历图直至图中所有和v有路径相通的顶点都被访问到。 v1 v1 v2 v3 v8 v7 v6 v4 v5 DFS 结果： 例1： → → → → → → → v2 v4 v8 v5 v3 v6 v7 起点 应退回到V8，因为V2已有标记 void DFS(Graph G, int v) {// 从顶点v出发，深度优先遍历G visited[v] = TRUE; VisitFunc(v); for(w=FirstAdjVex(G, v);w!=0; w=NextAdjVex(G,v,w)) if (!visited[w]) DFS(G, w); // 对v的尚未访问的邻接顶点w递归调用DFS } // DFS 对于无向图，这个算法可以遍历到v顶点所在的连通分量中的所有顶点，而与v顶点不在一个连通分量中的所有顶点遍历不到； 对于有向图可以遍历到起始顶点v能够到达的所有顶点。 若希望遍历到图中的所有顶点，就需要在上述深度优先遍历算法的基础上，增加对每个顶点访问状态的检测。 2、非连通图的深度优先有哪些信誉好的足球投注网站遍历 步骤： 访问起始点 v及图中所有和v有路径相通的顶点。 如果图中尚有顶点未被访问，则以该顶点为起始点，进行深度优先有哪些信誉好的足球投注网站遍历。重复上述过程，直至所有顶点都已被访问。 a b c h d e k f g F F F F F F F F F T T T T T T T T T a c h d k f e b g a c h k f e d b g 访问标志: 访问次序: 例2: 0 1 2 3 4 5 6 7 8 8 1 2 3 4 5 6 7 0 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) if (!visited[v]) DFS(G, v); // 对尚未访问的顶点调用DFS } （设图中有 n 个顶点，e 条边） （1）如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为O(n2)。 （2）如果用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。 结 论： 稠密图适于在邻接矩阵上进行深度优先遍历； 稀疏图适于在邻接表上进行深度优先遍历。 基本思想：——仿树的层次遍历过程。 Breadth_First Search 在访问了起始点v之后，依次访问 v的各个未曾访问过的邻接点； 然后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V有路径相通的顶点都被访问到。 若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有