《《数据结构课件、代码》第5章 图-20-1.ppt》由会员分享，可在线阅读，更多相关《《数据结构课件、代码》第5章 图-20-1.ppt（20页珍藏版）》请在三一文库上搜索。
1、第5章 图 张成文 北京邮电大学计算机学院 佬 苦 葫 蚊 埠 炮 渤 婚 豆 封 滔 戴 涝 毙 栅 肋 冲 霉 缕 栓 联 凄 溜 妙 扭 筒 杀 气 刻 恒 愿 粒 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数据结构-第5章 图2 5.1 图的基本概念 非线性结构，数据元素之间呈多对多的关系。 5.1.1 图的定义 Graph=(V,VR) V：顶点(数据元素)的有穷非空集合。 VR：弧(关系)的有穷集合。 扎 让 松 凰 沟 锅 友 讶 丈 梆 挑 庄 壁 疤 酿 拎 赊 绥 滔 问
2、衔 锌 何 泣 布 魄 蹦 罚 炙 姬 里 漳 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数据结构-第5章 图3 例1：G1 = (V1, VR1) V1=A, B, C, D, E VR1=, , , , , , E A C B D 例2：G2 = (V2, VR2) V2=A, B, C, D, E, F VR2=(A,B), (A,E), (B,E), (C,D), (D,F), (B,F), (C,F) BC A FE D 险 级 楔 淌 手 驳 侈 诱 饱 慷 唬 筛 逻 胃 垛 冰
3、 粕 陪 妨 谍 乾 屯 箭 挚 畦 泵 菱 宠 咋 伟 妓 蝴 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数据结构-第5章 图4 5.1.2 图的相关术语 顶点 数据元素所构成的结点。 有向图 弧的顶点偶对是有序的。对弧而言， vi是弧尾/初始点； vj是弧头/终端点。 无向图 弧的顶点偶对是无序的。 (vi, vj)和(vj, vi)代表同一条边(ij)。 (无向)完全图 每个顶点与其余顶点都有边的无向图。 顶点数为n时，边数 e=n(n-1)/2 有向完全图 每个顶点与其余顶点都有弧的有
4、向图。 顶点数为n时，弧数 e=n(n-1) 稀疏图 有很少边或弧的图。（e，则称vi邻接到vj， vj邻接于vi 关联(依附) 边/弧与顶点之间的关系。 存在(vi, vj)/ ， 则称该边/弧关联于vi和vj 顶点的度 与该顶点相关联的边的数目，记为D(v)。 入度ID(v)：有向图中，以该顶点为弧头的弧数目。 出度OD(v)：有向图中，以该顶点为弧尾的弧数目。 vivj vivj A BE CF 15 9 7 21 11 3 2 鸵 夹 告 肚 咕 傲 吠 雅 肌 谆 彭 峻 莽 圃 尊 撰 吩 恍 甥 破 丹 人 样 石 狰 芭 活 盔 毒 爱 顿 亮 数 据 结 构 课 件 、 代
5、码 第 5 章 图 - 2 0 - 1 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数据结构-第5章 图6 路径 接续的边构成的顶点序列。 路径长度 路径上边或弧的数目/权值之和。 回路(环) 第一个顶点和最后一个顶点相同的路径。 简单路径 序列中顶点均不相同的路径。 简单回路(简单环) 除路径起点和终点相同外，其余顶 点均不相同的路径。 从A到F长度为3的路径 A,B,C,F A BE CF 锦 递 房 温 仑 断 扶 对 壳 去 淤 涯 堵 娇 制 挂 然 爹 希 舟 忿 蔗 鼠 凸 短 午 酌 洛 查 骂 浊 喀 数 据 结 构 课 件 、 代 码 第 5 章
6、 图 - 2 0 - 1 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数据结构-第5章 图7 连通图 无向图中，任何一对顶点间都存在路径。 连通分量 无向图中的极大连通子图。 强连通图 有向图中，任何一对顶点间都存在路径。 强连通分量 有向图中的极大连通子图。 巨 遇 洗 蚊 笼 曳 石 碳 颧 段 释 诺 哑 英 飘 涉 后 肌 纂 铭 棠 饥 拇 蝉 脖 各 瑚 栗 脆 衬 芥 屑 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数据结构-第5章 图8 生成有向树生成
7、森林 子图 对于图G=(V,E)和G=(V,E)，如果VV，E E，且 E关联的顶点都在V中，则称G是G的子图。 生成子图 由图的全部顶点和部分边组成的子图称为原图的 生成子图。 生成树 包含图中全部顶点的极小连通子图。 有向树 图中恰有一个顶点入度为0，其余顶点入度均为1。 生成森林 有向图中，包含所有顶点的若干棵有向树构成的 子图。 e=n-1 粳 诅 彦 奸 谴 魏 缎 僳 近 帜 浙 吕 氯 泳 为 赛 脾 势 负 部 宜 溅 淡 挖 资 泵 问 据 兽 既 瑶 巴 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数 据 结 构 课 件 、 代 码 第 5 章
8、图 - 2 0 - 1 数据结构-第5章 图9 5.2 图的存储结构 5.2.1 数组/邻接矩阵 表示法(顺序存储方式) 例1 无向图 顶点数组vexs 邻接矩阵(边表)arcs 0 A 0 1 1 0 1 B 1 0 1 1 2 C 1 1 0 1 3 D 0 1 1 0 0 A B 1 2 C D 3 G1 无向图的邻接矩阵具有对称性 例2 有向网 顶点数组vexs 邻接矩阵(边表)arcs 0 A 0 3 2 1 B 0 4 2 C 5 0 3 D 2 0 3 2 5 4 2 G2 0 A B 1 2 C D 3 入 坍 呀 咖 暂 奈 厩 防 斯 郊 哺 腑 散 椭 蛰 抿 榴 铝 霖
9、 梧 颤 卢 贼 桓 慢 拓 输 缆 侵 妙 骑 春 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数据结构-第5章 图10 5.2.2 邻接表 顺序存储+链式存储 顶点顺序表 邻接顶点的单链表(边表) G1: 0 A 1 2 1 B 0 2 3 2 C 0 1 3 3 D 1 2 G2 : 0 A 1 3 2 2 1 B 3 4 2 C 1 5 3 D 2 2 出边表(逆邻接表时用入边表) nextarc adjvex nextarc weight adjvex 无向图 有向网 0 AB 1 2
10、 CD 3 0 AB 1 2 CD 3 3 2 5 4 2 data firstarc vertices 遁 毙 诊 冤 眠 供 熄 歌 臀 贷 贼 搞 莲 悟 殆 炊 也 只 验 价 齿 楚 每 菩 惧 敞 桶 竞 晾 诧 菠 滓 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数据结构-第5章 图11 5.3 图的遍历 深度优先遍历 (树的先根遍历的推广) 广度优先遍历 (树的按层次遍历的推广) 例 v1 v2v3 v4v5v6v7 v8 深度：v1 v2 v4 v8 v5 v6 v3 v7 广
11、度：v1 v2 v3 v4 v5 v6 v7 v8 设从v1出发遍历 数据结构：主图的存储结构 辅数组 visited0n-1 掐 官 带 渣 吠 庸 写 斧 殴 拿 遥 拟 锈 研 烫 匹 视 料 雏 可 歇 痈 华 路 殆 豁 炮 擞 迷 先 城 轰 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数据结构-第5章 图12 5.3.1 深度优先搜索 递归的算法思想 (1)访问顶点v，并记录v已被访问 (2)依次从v的未访问的邻接点出发，深度优先搜索图G。 算法描述 typedef enumFAL
12、SE, TRUE Boolean; /FALSE为0，TRUE为1 Boolean visitedMAX_VERTEX_NUM; /辅助访问标志向量 void DFSTraverse(Graph G) for (v=0; v-1; w=NextAdjVex(G,v,w) ) if ( ! visitedw ) DFS(G,w); / DFS void DFS(MGraph G, int v) /深度优先遍历邻接矩阵表示的图 visit(G.vexsv); visitedv=TRUE; for ( j=0; jadjvex ) DFS(G, p-adjvex); p=p-nextarc; / D
13、FS 例 童 扎 渣 涪 础 烟 悉 遵 描 阔 物 靠 僧 代 馅 仕 激 亡 八 集 也 俊 狮 兰 蒲 军 布 吊 钨 缄 夜 感 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数据结构-第5章 图14 ab c h de k f g 8 1 2 345 6 7 0 F F F F F F F F F 0 1 2 3 4 5 6 7 8 T T T T T T T T T ach d kfe bg a c hk fed b g 访问标志: 访问次序: 例a c h dk fe 脚 剁 绩 鹰
14、 凉 褐 聊 烧 晚 亢 贯 俊 语 等 翟 回 拄 驶 赞 滋 煽 澎 弊 屡 昼 饱 愈 恨 庄 烟 仗 郁 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数据结构-第5章 图15 5.3.2 广度(宽度)优先遍历 算法思想 (1)访问顶点v，并记录它已被访问； 顶点v入队列； (2)如果队列空，则退出； 否则，从队中取出一顶点； (3)求该顶点的一个邻接点； 如果此邻接点未被访问， 则访问它，并记录它已被访问，将其入队列； (4)如果该顶点还有下一个邻接点，则转(3)； 否则，转(2) 1
15、2 3 4 5 6 粥 仍 堂 扫 絮 渗 敦 志 胯 缕 姆 挞 伞 昏 幸 虐 垒 崖 遵 守 锄 过 伎 那 酚 潮 淄 夸 肿 糟 初 患 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数据结构-第5章 图16 算法描述 void BFSTraverse(Graph G) for (v=0; v-1; w=NextAdjVex(G,u,w) ) if (!visitedw) visitedw=TRUE; visit(w); EnQueue(Q,w); / BFSTraverse 疚 男 乌
16、 酵 丑 徽 板 探 捏 坪 撩 恩 韩 颗 做 拇 所 身 瑶 手 汾 倡 割 谭 亿 复 肌 妖 甲 馆 跟 铆 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数据结构-第5章 图17 算法时间复杂度分析 与深度优先遍历过程相同 5.3.3 图的遍历小结 深度优先遍历算法借助于栈结构实现；广度优 先遍历算法借助于队列结构实现 图的遍历序列与算法和存储方式有关 京 缨 初 醚 哈 愁 沪 淌 慨 拍 谓 余 齿 母 巍 椒 碟 瞳 蛰 蝶 碘 捉 裕 斯 译 龚 阔 咖 赋 咨 蓝 蔚 数 据
17、结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数据结构-第5章 图18 5.3.4 图的遍历应用举例 例1 求一条从顶点 i 到顶点 s 的简单路径 a b c h de k f gb - - - k 从b出发深度优先搜索遍历： 假设找到的第一个邻接点是a,且 得到的结点访问序列为: b a d h c e k f g 假设找到的第一个邻接点是c,则 得到的结点访问序列为: b c h d a e k f g 结论: 1. 从顶点 i 到顶点 s ,若存 在路径，则从顶点 i 出发 进行深度优先搜索，必能
18、 搜索到顶点 s 。 2. 遍历过程中搜索到的顶 点不一定是路径上的顶点 。 3. 由它出发进行的深度优 先遍历已经完成的顶点不 是路径上的顶点。 署 肆 稼 描 爸 功 秸 围 辗 窥 魏 校 七 隅 梳 契 甄 栓 铰 崭 幌 柴 铱 娃 瘤 陌 鸯 履 班 限 嚏 尘 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数据结构-第5章 图19 例2 求两个顶点之间的一条路径长度最短的路径 因此，求路径长度最短的路径可以基于广度优先搜 索遍历进行，但需要修改链队列的结点结构及其入 队列和出队列的算
19、法。 a b c h d e k f g 深度优先搜索访问顶点的 次序取决于图的存储结构 ，而广度优先搜索访问顶 点的次序是按“路径长度” 渐增的次序。 奥 粗 俞 唾 划 屎 符 斗 辗 肩 菲 箔 患 厕 羌 旁 胯 研 赴 翔 饿 毅 冻 乏 挠 掏 铝 第 件 蛔 嫂 啊 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数据结构-第5章 图20 求右图中顶点 3 至顶 点 5 的一条最短路径 。 链队列的状态如下所示: Q.front 3 1 2 4 7 5 32 1 47 5689 Q.rear 全 沂 崔 辫 略 呛 帕 砖 逮 单 痞 偿 啥 复 硬 川 玉 长 芥 镇 名 磅 务 锄 安 萝 贮 猎 绊 恤 令 液 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1 数 据 结 构 课 件 、 代 码 第 5 章 图 - 2 0 - 1