数据结构chap7.pptVIP

图 存储结构 遍 历 邻接矩阵 邻 接 表 十字链表 邻接多重表 深度优先有哪些信誉好的足球投注网站DFS 广度优先有哪些信誉好的足球投注网站 BFS 无向图的应用 应用 图的连通分量 图的生成树 最小生成树 Prim算法 Kruskal算法 有向(无环)图的应用 最短路径 Dijkstra算法 Floyd算法 （利用DFS） 本章小结 (利用DFS和BFS) * * * ∞ 讨论3：在图的邻接表中如何进行DFS？ v0 → v1 → v2 → v3 DFS 结果 0 0 0 0 0 1 2 3 辅助数组 visited [n ] 1 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1 例： —照样借用visited [n ]！ 起点 0 1 2 3 注意：在邻接表中，并非每个链表元素（表结点）都被扫描到,遍历速度很快。 深度优先遍历图的算法: 课本P169页 Boolean visited [MAX]; // 访问标志数组 Status (*VisitFunc) (int v); //函数变量 Void DFSTraverse( Graph G, Status (*Visit) (int v)) { // 对图G做深度优先遍历 VisitFunc = Visit; // 使用全局变量VisitFunc,使DFS不必设函数指针参数 for (v=0; vG.vexnum; ++v) visited[v] = FALSE; // 访问标志数组初始化 for (v=0; vG.vexnum; ++v) if (!visited[v]) DFS(G,v); // 对尚未访问的顶点调用DFS } Void DFS (Graph G, int v) { // 从第v个顶点出发递归地深度优先遍历图G visited [v] = TRUE; VisitFunc (v); //访问第v个顶点 for ( w = FirstAdjVex(G,v); w; w = NextAdjVex(G,v,w) ) if (!visited[w]) DFS(G,w); // 对v的尚未访问的邻接点w递归调用DFS } DFS 算法效率分析: （设图中有 n 个顶点，e 条边） 如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为O(n2)。 如果用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。 结论： 稠密图适于在邻接矩阵上进行深度优先遍历； 稀疏图适于在邻接表上进行深度优先遍历。 二、广度优先有哪些信誉好的足球投注网站( BFS ) 基本思想：——仿树的层次遍历过程。 Breadth_First Search v1 v1 v2 v3 v8 v7 v6 v4 v5 BFS 结果 例1： → → → → v2 v3 → v4 v5 → v6 v7 → v8 例2： v3 → BFS 结果 v4 → v5 → 起点 遍历步骤 起点 v2 → v1 → v6 → v9 → v8 → v7 广度优先有哪些信誉好的足球投注网站（遍历）步骤： 简单归纳： 在访问了起始点v之后，依次访问 v的邻接点； 然后再依次访问这些顶点中未被访问过的邻接点； 直到所有顶点都被访问过为止。 广度优先有哪些信誉好的足球投注网站是一种分层的有哪些信誉好的足球投注网站过程，每向前走一步可能访问一批顶点，不像深度优先有哪些信誉好的足球投注网站那样有回退的情况。因此，广度优先有哪些信誉好的足球投注网站不是一个递归的过程，其算法也不是递归的。 讨论1：计算机如何实现BFS？ 邻接表 ——除辅助数组visited [n ]外，还需一辅助队列！ 例： 起点 辅助队列 v2已访问过了 BFS 遍历结果 入队！ 初始f=n-1,r=0 讨论2： BFS算法如何编程？ Void BFSTraverse( Graph G, Status (* Visit) (int v) ) { for ( v=0; vG.vexnum; ++v ) visited[v] = FALSE ; InitQueue(Q); // 置空的辅助队列Q for ( v=0; vG.vexnum; ++v ) if (!visited[v