图的遍历及生成树.ppt

第7章图7 1图的定义和术语7 2图的存储结构7 3图的遍历 重点 难点 7 4图的连通性问题7 5有向无环图及其应用7 6最短路径 期末考试 长春工业大学 数据结构精品课程网站 习题解析 7 3图的遍历 从图中某一顶点出发访遍图中其余顶点 且使每一个顶点仅被访问一次 这一过程就叫做图的遍历 图的遍历操作要解决的关键问题 1 在图中 如何选取遍历的起始顶点 在图中 任何两个顶点之间都可能存在边 顶点是没有确定的先后次序的 所以 顶点的编号不唯一 这里指按顶点的存储顺序 解决方案 从编号小的顶点开始 2 因图中可能存在回路 在访问完某个顶点之后会沿着某些边又回到了曾经访问过的顶点 那么如何避免顶点的重复访问 解决方案 附设访问标志数组visited 0 n 1 它的初始状态为0 在图的遍历过程中 一旦某一个顶点i被访问 就立即改visited i 为1 防止它被多次访问 1 深度优先搜索 DFS Depth FirstSearch 基本思想 1 从图中某顶点V0出发 访问此顶点 然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图 直至图中所有和V0有路径相通的顶点都被访问到 2 若此时图中尚有顶点未被访问 则另选图中一个未曾被访问的顶点作起始点 3 重复上述两步 直至图中所有顶点都被访问到为止 与树的先序遍历过程类似 详细过程 1 1 1在访问图中某一起始顶点v后 由v出发 访问它的任一邻接顶点w1 1 2再从w1出发 访问与w1邻接但还未被访问过的顶点w2 1 3然后再从w2出发 进行类似的访问 直至到达所有的邻接顶点都被访问过的顶点u为止 2 退回一步 退到前一次刚访问过的顶点 看是否还有其它未被访问的邻接顶点 2 1如果有 则访问此顶点 之后再从此顶点出发 返回第1 步的操作 2 2如果没有 就再退回一步进行搜索 2 3重复上述过程 直到连通图中所有顶点都被访问过为止 例 从顶点v1出发 DFS下图 访问序列 v1 v2 v4 v8 v5 v3 v6 v7 图的DFS算法一般描述intvisited MAXVEX 访问标志数组voidDFSTraverse GraphG 对图G作深度优先遍历for v 0 v G vexnum v visited v FALSE 访问标志数组初始化0for v 0 v G vexnum v if visited v DFS G v 对尚未访问的顶点调用DFS voidDFS GraphG intv 从第v个顶点出发递归地深度优先遍历图Gvisited v TRUE Visit v 访问第v个顶点 对v的尚未访问的邻接顶点w递归调用DFSfor w FirstAdjVex G v w 0 w NextAdjVex G v w if visited w DFS G w 用邻接表实现图的深度优先搜索 0123456789 在图的邻接表中如何进行DFS DFS结果 辅助数组visited n 例 照样借用visited n 起点 0123 注意 在邻接表中 并非每个链表元素 表结点 都被扫描到 因此遍历速度很快 v0 v1 v2 v3 voidDFS ALGraphG intv ArcNode p visited v 1 置已访问标记 printf d v 输出被访问顶点的编号 p G vertices v firstarc p指向顶点v的第一个邻接点 while p NULL if visited p adjvex 0 DFS G p adjvex 若p adjvex顶点未访问 递归访问它 p p nextarc p指向顶点v的下一个邻接点 邻接表的DFS算法 for j 0 j G vexnum j if G arcs v j DFS1 DFS1 MGraphG intv visit v visited v 1 G arcs n n 为邻接矩阵 v为起始顶点 编号 访问 例如打印 顶点v G arcs v j 1有邻接点 visited n 0未访问过 访问后立即修改辅助数组标志 从v所在行从头搜索邻接点 邻接矩阵的DFS算法 分析 在遍历图时 对图中每个顶点至多调用一次DFS函数 因为一旦某个顶点被标志成已被访问 就不再从它出发进行搜索 因此 遍历图的过程实质上是对每个顶点查找其邻接点的过程 其耗费的时间则取决于所采用的存储结构 如果用邻接矩阵来表示图 遍历图中每一个顶点都要从头扫描该顶点所在行 因此遍历全部顶点所需的时间为O n2 如果用邻接表来表示图 虽然有2e个表结点 但只需扫描e个结点即可完成遍历 加上访问n个头结点的时间 因此遍历图的时间复杂度为O n e 2 广度优先搜索 BFS Breadth FirstSearch 基本思想 从图中某个顶点V0出发 并在访问此顶点后依次访问V0的所有未被访问过的邻接点 之后按这些顶点被访问的先后次序依次访问它们的邻接点 直至图中所有和V0有路径相通的顶点都被访问到 若此时图中尚有顶点未被访问 则另选图中一个未曾被访问的顶点作起始点 重复上述过程 直至图中所有顶点都被访问到为止 与树的层次遍历过程类似 例 从顶点v1出发 BFS下图 访问序列 v1 v2 v3 v4 v5 v6 v7 v8 用邻接表实现图的广度优先搜索 BFS非递归算法 voidBFSTraverse GraphG Status Visit intv 使用辅助队列Q和访问标志数组visited v for v 0 v G vexnum v visited v FALSE InitQueue Q 置空的辅助队列Qfor v 0 v G vexnum v if visited v v尚未访问visited v TRUE Visit v EnQueue Q v v入队 while QueueEmpty Q DeQueue Q u 队头元素出队并置为ufor w FirstAdjVex G u w 0 w NextAdjVex G u w if visited w w为u的尚未访问的邻接顶点visited w TRUE Visit w EnQueue Q w if while if BFSTraverse 分析 每个顶点至多进一次队列 遍历图的过程实质上是通过边或弧找邻接点的过程 因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同 两者不同之处仅仅在于对顶点访问的顺序不同 邻接矩阵 O n2 邻接表 O n e 第7章图7 1图的定义和术语7 2图的存储结构7 3图的遍历7 4图的连通性问题7 5有向无环图及其应用7 6最短路径 7 4图的连通性问题 1 无向图的连通分量和生成树2 最小生成树普里姆算法克鲁斯卡尔算法 要想判定一个无向图是否为连通图 或有几个连通分量 通过对无向图遍历即可得到结果 连通图 仅需从图中任一顶点出发 进行深度优先搜索 或广度优先搜索 便可访问到图中所有顶点 无向图的连通性 1 无向图的连通分量和生成树 非连通图 需从多个顶点出发进行搜索 而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集 基本概念生成树 某连通分量的极小连通子图 它含有图中全部顶点 但只有n 1条边 生成森林 非连通图的各个连通分量的极小连通子图 即生成树 构成的集合 含全部顶点 但构成这些树的边是最少的 思考1 若对连通图进行遍历 得到的是什么 遍历过程中历经的边的集合和图G中所有顶点一起构成连通图G的极小连通子图 即图的生成树 由深度优先搜索得到的生成树 称为深度优先搜索生成树 由广度优先搜索得到的生成树 称为广度优先搜索生成树 思考2 若对非连通图进行遍历 得到的是什么 得到的将是各连通分量的生成树 即图的生成森林 a 深度优先生成树 b 广度优先生成树 生成树 例 求下图的深度优先生成树和广度优先生成树 对非连通图 每个连通分量中的顶点集和遍历时走过的边一起构成若干棵生成树 这些连通分量的生成树组成非连通图的生成森林 例 一个连通图的生成树可能不唯一 由不同的遍历次序 从不同顶点出发进行遍历都会得到不同的生成树 深度优先生成森林 广度优先生成森林 1 理解并掌