数据结构-图的遍历

图的遍历 深度优先搜索 广度优先搜索 图的遍历 小结和作业 复习 课堂练习 复习 图的存储结构 复习 图的存储结构 复习 图的存储结构 复习 图的存储结构 复习 图的存储结构 复习 图的存储结构 markivexilinkjvexjlink 复习 图的存储结构 012 存储结构的比较 邻接矩阵可用于DG UDG DN UDN邻接表可用于DG UDG DN UDN十字链表用于DG和DN邻接多重链表用于UDG和UDN 一 应用范围 存储结构的比较 邻接矩阵 n n2邻接表用于DG和DN n e或者n 2e 用于UDG和UDN n 2e十字链表 n e邻接多重链表 n e 二 存储空间 存储结构的比较 三 对操作的支持 1 对顶点的访问 LocateVex G u 返回u的位置 GetVex G v 返回v的值 PutVex 对u赋值value 存储结构的比较 2 插入和删除顶点 都要对存放顶点数组元素的操作但是对邻接矩阵 还要修改邻接矩阵 InsertVex 在图G中增添新顶点v DeleteVex 删除G中顶点v及其相关的弧 存储结构的比较 3 插入和删除弧 InsertArc DeleteArc 存储结构的比较 邻接矩阵 修改边 以及 邻接表 无向图 修改两个顶点的链表 有向图 修改一个 或两个 顶点的链表十字链表 涉及两个链表多重邻接表 涉及两个链表 存储结构的比较 4 邻接点 FirstAdjVex G v 返回v的 第一个邻接点 若该顶点 在G中没有邻接点 则返回 空 NextAdjVex G v w 返回v的 相对于w的 下一个邻接 点 若w是v的最后一个邻接点 则 返回 空 存储结构的比较 邻接矩阵 第v行邻接表 第v个链表十字链表 第v个链表多重邻接表 第v个链表 存储结构的比较 邻接矩阵 第v行邻接表 第v个链表十字链表 第v个链表多重邻接表 第v个链表 4 邻接边 邻接点函数的实现 FirstAdjVex G v 返回第1个邻接点的位置 没有邻接点 返回 1 NextAdjVex G v w 返回w后面的邻接点的位置 邻接点函数的实现 intfirstAdjVex ALGraghG intv p G vertices v firstarc v的第1个邻接点if p return 1 无邻接点returnp adjvex 邻接点函数的实现 intnextAdjVex ALGraghG intv intw p G vertices v firstarc v的第1个邻接点while p 用C语言描述存储结构 1 图的二个参数 顶点个数 边数 弧数 Vertex Vertices vexnum Edge arc arcnum edgenum 2 图的第三个参数 图的类型 GraphKind DG UDG DN UDN 图的遍历 定义 从图中某个顶点出发游历图 访遍图中其余顶点 并且使图中的每个顶点仅被访问一次的过程 用途 是解决图的连通性 拓扑排序和求关键路径等算法的基础 深度优先搜索 广度优先搜索 分类 深度优先搜索 W1 W2和W3均为V的邻接点 SG1 SG2和SG3分别为含顶点W1 W2和W3的子图 深度优先搜索 访问顶点V for W1 W2 W3 若邻接点Wi未被访问 则从它出发进行深度优先搜索历 深度优先搜索 连通图 深度遍历序列 V1 V2 V4 V8 V5 V6 V3 V7 V1 V2 V4 V5 V3 V7 V6 V8 深度优先搜索 深度优先搜索 深度优先搜索 1 从深度优先搜索遍历连通图的过程类似于树的先根遍历2 对图G深度优先搜索得到的顶点序列不是唯一的 3 搜索过程中经过的边和所有的顶点构成了图的一棵生成树 4 如何判别V的邻接点是否被访问 为每个顶点设立一个 访问标志visited w 深度优先搜索 连通图 voidDFS GraphG intv 从顶点v出发 深度优先搜索遍历连通图Gvisited v TRUE for w FirstAdjVex G v w 0 w NextAdjVex G v w if visited w DFS G w 对v的尚未访问的邻接顶点w递归调用DFS DFS 深度优先搜索 连通图 voidDFS GraphG intv 从顶点v出发 深度优先搜索遍历连通图Gvisited v TRUE for w FirstAdjVex G v w 0 w NextAdjVex G v w if visited w DFS G w 对v的尚未访问的邻接顶点w递归调用DFS DFS 深度优先搜索 连通图 V1 V2 V3 V4 V5 V1 V2 V8 V5 V6 V4 V2 V8 V8 V3 V1 V6 V7 V3 V8 按照完成DFS的先后 顶点的次序是 V5 V7 V3 V6 V8 V4 V2 V1 DFS G V1 V7 voidDFS GraphG intv 非递归算法InitStack S visited FALSE 所有的顶点尚未被访问过Push S v while Empty S Pop S u if visited u visit u visited u TRUE for w FirstAdjVex G u w 0 w NextAdjVex G u w if visited w Push G w 将没访问的邻接点压栈 DestroyStack S DFS 深度优先搜索 连通图 深度优先搜索 非连通图 首先将图中每个顶点的访问标志设为FALSE 之后搜索图中每个顶点 如果未被访问 则以该顶点为起始点 进行深度优先搜索遍历 否则继续检查下一顶点 深度优先搜索 非连通图 a c h d k f e b g 访问次序 8 1 2 3 4 5 6 7 0 a c h d k f e b g T T T T T T T T T 访问标志 a b c h d e k f g 深度优先搜索 非连通图 voidDFSTraverse GraphG intv for v 0 v G vexnum v visited v FALSE 访问标志数组初始化for v 0 v G vexnum v if visited v DFS G v 对尚未访问的顶点调用DFS 深度优先搜索 1 从图中某个顶点V0出发 访问此顶点 2 然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图 直至图中所有与V0有路径的顶点都被访问到 3 如果图中还有顶点未被访问 则令选一个未曾被访问的顶点作为起始点 重复上述过程 直至图中所有顶点都被访问到 广度优先搜索 对连通图 从起始点V到其余各顶点必定存在路径 其中 V w1 V w2 V w8的路径长度为1 V w7 V w3 V w5的路径长度为2 V w6 V w4的路径长度为3 w1 w8 w3 w7 w6 w2 w5 w4 广度优先搜索 1 从图中的某个顶点V0出发 并在访问此顶点之后依次访问V0的所有未被访问过的邻接点 2 然后按这些顶点被访问的先后次序依次访问它们的邻接点 直至图中所有和V0有路径相通的顶点都被访问到 3 若此时图中尚有顶点未被访问 则另选图中一个未曾被访问的顶点作起始点 4 重复上述过程 直至图中所有顶点都被访问到为止 广度优先搜索 V1 V8 广度遍历序列 V4 V6 V8 V2 V5 V1 V3 V7 V2 V3 V4 V5 V6 V7 广度优先搜索 V1 V2 V4 V5 V3 V7 V6 V8 V1 V8 广度遍历序列 V2 V3 V4 V5 V6 V7 广度优先搜索 V1 V2 V4 V5 V3 V7 V6 V8 V1 V8 广度遍历序列 V2 V3 V4 V6 V7 V5 广度优先搜索 voidBFSTraverse GraphG Status Visit intv for v 0 v G vexnum v visited v FALSE 初始化访问标志InitQueue Q 置空的辅助队列Qfor v 0 v G vexnum v if visited v v尚未访问 BFSTraverse 广度优先搜索 visited v TRUE Visit v 访问uEnQueue Q v v入队列while QueueEmpty Q DeQueue Q u 队头元素出队并置为ufor w FirstAdjVex G u w w NextAdjVex G u w if visited w visited w TRUE Visit w EnQueue Q w 访问的顶点w入队列 if while 课堂练习 1 无向图G V E 其中 V a b c d e f E a b a e a c b e c f f d e d 对该图进行深度优先遍历 得到的顶点序列正确的 A a b e c d fB a c f e b dC a e b c f dD a e d f c b a b e d c f 2 已知一无向图G V E 其中V a b c d e E a b a d a c d c b e 现用某一种图遍历方法从顶点a开始遍历图 得到的序列为abecd 则采用的是 课堂练习 a d b e c 小结和作业 图的遍历定义 用途 图的深度优先搜索 图的广度优先搜索 作业 7 4 7 22 图的遍历方法 深度优先搜索 连通图 栈的变化 V1 V3 V2 V3 V5 V4 V3 V5 V8 V