门户网站wordpress哪个比较好,wordpress等待加载动画设置,全国企业信息网查询平台官网,dw 做的网站能用吗第 6 章 图 【考纲内容】 1.图的基本概念 2.图的存储及基本操作#xff1a;(1) 邻接矩阵法#xff1b;(2) 邻接表法#xff1b;(3) 邻接多重表、十字链表 3.图的遍历#xff1a;(1) 深度优先搜索#xff1b;(2) 广度优先搜索 4.图的基本应用#xff1a;(1) 最小 (代价) 生… 第 6 章 图 【考纲内容】 1.图的基本概念 2.图的存储及基本操作(1) 邻接矩阵法(2) 邻接表法(3) 邻接多重表、十字链表 3.图的遍历(1) 深度优先搜索(2) 广度优先搜索 4.图的基本应用(1) 最小 (代价) 生成树(2) 最短路径(3) 拓扑排序(4) 关键路径 【考情统计】 年份 题数及分值 考点 单选题 综合题 总分值 2009 1 1 12 无向连通图的特性、最短路径新的算法 2010 2 0 4 连通图的特性、拓扑排序 2011 1 1 10 图的基本概念、邻接矩阵、拓扑序列、关键路径 2012 4 0 8 图的存储表示法、广度优先遍历、最小生成树性质、Prim 和 Kruskal 算法、拓扑排序、最短路径Dijkstra 2013 3 0 6 邻接矩阵、广度优先遍历、关键路径 2014 1 1 12 图的基本概念、图的存储、拓扑排序、最短路径Dijkstra 2015 2 1 12 广度优先遍历、最小生成树Prim 和 Kruskal、邻接矩阵 2016 3 0 12 邻接表、深度优先遍历、拓扑排序、最短路径Dijkstra 2017 1 1 10 无向图边数和顶点数的关系、最小生成树Prim 2018 1 1 14 拓扑排序、最小生成树Prim 或 Kruskal 2019 2 0 4 有向无环图描述表达式、关键路径 2020 3 0 6 深度优先遍历、拓扑排序、最小生成树Kruskal、关键路径 2021 2 1 19 拓扑排序、最短路径Dijkstra、邻接矩阵分析与应用 2022 2 0 4 图的基本概念、关键路径 2023 1 1 15 最短路径、图的基本概念 2024 1 1 15 邻接多重表、拓扑排序算法题 【考点解读】 本章内容是数据结构考试重点之一每年必考出题形式有选择题与综合应用题。①图的基本应用是本章的重点内容408 真题中每年都会有相关考查。考生应该熟练掌握图的基本应用小节里的相关算法算法思想及算法代码都要掌握。②真题也常考各种图相关算法的实现细节例如广度优先遍历和深度优先遍历的过程、Prim 算法和 Kruskal 算法实现过程的对比、Dijkstra 算法实现过程等。③本章第一小节 “图的基本概念” 常在图的各类计算题中考查考生应熟练的掌握本章第一小节中的所有概念名词。 另外需要引起 408 考生高度重视的是图的算法题自 2021 年 408 首次考察以来最近几年2021 年、2023 年和 2024 年的 408 考试中均在考察图的算法题。但在 2021 年之前连续十几年 408 考试都没考过图的算法题。尤其是 2024 年 408 考试突然考察拓扑排序的算法题令很多考生猝不及防几乎是得 0 分。所以图的算法题考生务必高度重视不再是可以忽视的部分。考生不要只停留在只掌握算法思想不仅要会手动模拟选择题常考还应该熟练掌握图相关的算法代码应对算法题会灵活运用图的相关的算法。 【复习建议】 本章要注意理解并掌握图的基础概念和各种图的应用。复习建议如下 1.各种图的定义和图相关的概念是本章的基础。重要知识点为出入度和度的概念以及这三者之间的关系、图的连通性、生成树概念、图的相关计算。 2.图的存储结构考生除了掌握四种常用图的存储结构之外还需分辨出这四种存储方式的优缺点。其中邻接矩阵和邻接表是考查的重点后两者只需理解思想即可。 3.需要掌握图的两种遍历方式加深理解为什么图的遍历需要访问数组这也是区分树与图的遍历很重要的一点。 4.图的四种应用分别为最小生成树涉及 Prim 算法和 Kruskal 算法、最短路径Dijkstra 算法和 Floyd 算法、拓扑排序、关键路径。考生需要掌握这些应用的思想并要求能根据具体题目进行手动推导答案出题较为灵活经常结合本章节其他小节的内容进行综合考查。 6.1 图的基本概念 6.1.1 图的定义 图 G 由两个集合 V(vertex) 和 E(edge) 组成记为 G(V,E)。其中V 是 G 的顶点集合记为 V(G)E 是连接 V 中两个不同顶点顶点对的边的有限集合记为 E(G) ¹。若用顶点表示对象则边表示对象间关系。 【提示】图 G 的边集 E(G) 可以是空集但顶点集 V(G) 不能为空集。 通常用符号 v,w 表示从顶点 v 到顶点 w 的一条边。 若表示边的顶点对是有序的则称该图为有向图 ¹。在有向图中v,w 和 w,v 分别表示两条不同的边。 有向图的边 v,w 也称为弧顶点 v 是边的起点也称为弧尾顶点 w 是边的终点也称为弧头有箭头的一方。 【提示】弧头和弧尾的概念跟通常理解的不一样弧头是箭头 (→) 指向的一方不要弄混了。 例如在图 6.1-(a) 中的弧 V2,V1顶点 V1 是弧头顶点 V2 是弧尾。 例如图 6.1-(a) 所示的有向图 G 可表示为 G(V(G),E(G)) V(G){V1,V2,V3,V4} E(G){V2,V1,V1,V3,V1,V4,V3,V4,V4,V2} 若表示边的顶点对是无序的v,w 和 w,v 表示同一条边则称该图为无向图。为了跟有向图区分通常用符号 (v,w) 表示无向图中从顶点 v 到顶点 w 的一条边。 例如图 6.1-(b) 所示的无向图 G 可表示为 G(V(G),E(G)) V(G){V1,V2,V3,V4} E(G){(V1,V2),(V3,V1),(V4,V1),(V3,V4),(V4,V2)} 6.1.2 图的基本术语 1.顶点的度、出度和入度 在无向图中某个顶点的度Degree指与该顶点相连的边的条数。 例如在图 6.1-(b) 所示无向图中顶点 V₁、V₂、V₃、V₄的度分别为3223。 在有向图中以顶点 v 为终点即指向顶点 v以顶点 v 为弧头的边数目称为顶点 v 的入度 ¹。以顶点 v 为起点即以顶点 v 为弧尾的边数目称为顶点 v 的出度 ¹。在有向图中某个顶点的度等于该顶点的入度与出度的和。 例如在图 6.1-(a) 所示有向图中顶点 V₁的度为 3顶点 V₁入度为 1顶点 V₁出度为 2。 关于顶点的度有如下结论 ①在有向图或无向图中因为每条边都要连接两个顶点所以边总条数的两倍等于所有顶点的度之和。但全部顶点数目之和不一定等于边数的两倍 (例如图中只有一个顶点没有边)。 ②在有向图中所有顶点的出度的和等于所有顶点的入度的和。 ③在无向或有向图中奇数度的顶点的个数是偶数。由①知所有顶点的度之和是偶数又因偶数度顶点的度之和为偶故奇度顶点的度之和亦偶所以奇度顶点的个数必偶。 2.完全图 无向完全图图中任意两个顶点都有边相连。n 个顶点的无向完全图共有 n (n - 1)/2 条边。 有向完全图图中任意两个顶点都有两条方向相反的边相连。n 个顶点的有向完全图共有 n (n - 1) 条边。 3.稠密图和稀疏图 稠密图和稀疏图是一个主观的概念。边数较少如边的条数 E 远小于 V² 的图称为稀疏图反之称为稠密图 ²。 4.路径和路径长度 路径指从一个顶点开始经过一系列的边到达另一个顶点形成的顶点序列。 路径长度指路径上的边的条数。例如图 6.1-(a) 中顶点 V₁到顶点 V₂之间的路径有 2 条{V₁、V₄、V₂} 和 {V₁、V₃、V₄、V₂}路径长度分别为 2 和 3。 5.回路或环 回路环指起点和终点是同一个顶点的路径。回路也称为环。例如在图 6.1-(a) 中路径 {V₁、V₃、V₄、V₂、V₁} 是一条回路。 6.子图 子图若图 G′的顶点集和边集分别为图 G 顶点集和边集的子集则图 G′称为图 G 的子图。 【注意】子图首先得是个图图 G 的顶点集 V 的任意子集 V′与边集 E 的任意子集 E′不一定能构成图 G 的子图因为 (V′, E′) 不一定能构成一个图。例如顶点集 V′ {V₂,V₃} 是图 6.1-(a) 顶点集的子集E′ {V₁,V₃,V₃,V₄} 是图 6.1-(a) 边集的子集但 (V′, E′) 不是图 6.1-(a) 的子图因为 (V′, E′) 不能构成一幅图。 7.连通连通图极大连通子图连通分量 连通指两个顶点间存在路径。 连通图若图 G 中任意两个顶点都是连通的则称 G 为连通图否则称为非连通图 ³。若一个图 G 有 n 个顶点边的条数小于 n - 1则 G 必为非连通图。 连通子图同时满足连通图和子图的定义。 极大连通子图极大连通子图是不被另外任何一个连通子图所包含的子图。无向图 G 的极大连通子图称为 G 的连通分量 ³。连通图 G 存在唯一的连通分量即图 G 本身。非连通图的连通分量不唯一。 例如在图 6.2 中①图 (a)、(b) 均为连通图且图 (a) 是自身的极大连通子图图 (b) 是自身的极大连通子图②图 (a) 和图 (b) 共同组成一张图 (c)顶点 B 到顶点 H 之间不存在路径所以图 (c) 是非连通图。在图 (c) 中有两个连通分量 (即有两个极大连通子图)分别为图 (a) 和图 (b)。 8.极小连通子图生成树生成森林 极小连通子图指图的某一个顶点子集所确定的连通子图中包含边数最少的连通子图。 生成树连通图的生成树是含有图中全部的 n 个顶点和 n - 1 条边的极小连通子图。若随机去掉生成树的一条边则该生成树会变成非连通图。若随机添一条边则该生成树会形成一个环。 生成森林对于非连通图 G 而言连通分量的生成树构成了图 G 的生成森林。 9.强连通图强连通分量 强连通图任意两个顶点间都存在路径的有向图。 【提示】一个图是强连通并不一定说明图中任意两个顶点之间都存在双向边是允许有其他顶点作为中间顶点的。 强连通分量有向图的极大强连通子图 ²。 10.边的权网带权图 边的权在无向图或有向图的每一条边上都可以标上一个代表某种含义的数值该数值称为边的权 ²。例如用边来表示活动那么边的权值可以表示完成该活动的时间开销完成该活动的费用等。 网指边上带有权值的图也称为带权图 ³。 6.1.3 习题精编 1.无向图 G (V,E)若图 G 的顶点数和边数相等则图 G 一定是 。 A. 连通图 B. 非连通图 C. 无环的图 D. 有环的图 2.以下关于图的叙述中正确的是 。 A. 图与树的区别在于图的边数大于等于顶点数 B. 假设图 G (V,E)顶点集 V′⊆VE′⊆E则 V′和 E′构成 G 的子图 C. 无向图的连通分量是指向无图中的极大连通子图 D. 图的遍历就是从图中某一顶点出发并访问图中其余顶点 2.【参考答案】 C 【解析】 A 错误因为图和树的区别是逻辑上的区别二者的定义不同而不能只依靠边数和顶点数的多少来判断谁是树谁是图。B 错误该选项具有很强的迷惑性看似是和子图的定义相差无几不过仔细看可以发现若集合 E′中的边对应的顶点不是 V′的元素则 V′和 E′依然构不成子图。C 正确。D 错误迷惑性很强。图的遍历是每个顶点最多只会被访问一次若图非连通只从某一顶点出发不一定能够访遍所有顶点。 3.以下关于图的叙述中正确的是 。 A. 强连通有向图的任何顶点到其他所有顶点都有弧 B. 图的任意顶点的入度等于出度 C. 有向完全图一定是强连通有向图 D. 有向图的边集的任意子集和顶点集的任意子集均可构成原有向图的子图 3.【参考答案】 C 【解析】 A 错误强连通有向图是任何顶点到其他所有顶点都有路径而不一定都有弧。B 错误图包含有向图和无向图有向图的任意顶点的入度不一定等于出度无向图才满足。C 正确。D 错误若边集的子集中边的顶点元素不在顶点集的子集里则有向图的边集的子集和顶点集的子集仍然构不成原有向图的子图。 4.若图 G 为非连通无向图含有 15 条边则图 G 至少有 个顶点。 A. 6 B. 7 C. 8 D. 9 4.【参考答案】 B 【解析】 关键词 “至少”“非连通”。假设满足题意的无向图至少有 n 1 个顶点。首先考虑含有 n 个顶点且一定为连通图的情况满足条件的图为完全图含有 15 条边然后再加上一个顶点则可得到此时的非连通图至少含有的顶点个数。所以15 (n - 1) n/2解得 n 等于 6因此 15 条边的非连通无向图至少有 6 1 7 个顶点选择 B。 5.强连通有向图 G₁和连通无向图 G₂都含有 n 个顶点则 G₁和 G₂最少边条数分别为 。 A. nn - 1 B. n (n - 1)n - 1 C. nn D. n (n - 1)n 5.【参考答案】 A 【解析】 若图构成连通无向图则边数最少的情况是构成一棵树则至少有 n - 1 条边若是强连通有向图则边数最少的情况是构成一个有向环即有 n 条边。选择 A。 6.无向图 G 有 100 条边度为 9 和度为 11 的顶点均各有 10 个其余都是度为 3 的顶点则图 G 共有 个顶点。 A. 20 B. 23 C. 26 D. 29 6.【参考答案】 A 【解析】 在 n 个顶点e 条边的无向图中每个顶点的度之和等于边数的两倍。因此可得 (9 * 10) (11 * 10) (n - 10 - 10) * 3 100 * 2解得 n 20选择 A。 7.若有向图 G (V,E) 的顶点数为 n。则 G 每个顶点的入度和出度之和最大值可是 。 A. n B. n - 1 C. 2n D. 2n - 2 7.【参考答案】 D 【解析】 每个顶点可以和其他 n - 1 个顶点都有边相连对应每一个出度且每条边都可以有两个方向相反的边对应每一个入度因此最多可以有 2 (n - 1) 条边每条边对应一个度。 8.具有 6 个顶点的无向图当有 条边时能确保是一个连通图。 A. 8 B. 9 C. 10 D. 11 8.【参考答案】 D 【解析】 当 5 个顶点的无向图为完全图时再加上一条边连接另外的第 6 个顶点此时能用最少的边确保该图是连通图。共需 11 条边选择 D。 9.设有无向图 G (V,E) 和 G′(V′,E′)若 G′是 G 的生成树则下列不正确的是 。 I. G′一定是 G 的子图 II. G′为 G 的连通分量 III. G′为 G 的无环子图 IV. G′为 G 的极小连通子图且 V′ V A. 只有 IV B. II、III C. III、IV D. 只有 II 9.【参考答案】 D 【解析】 II 错误无向图的极大连通子图称为连通分量而一个连通图的生成树是极小连通子图。又因此极小连通子图是无环的。所以 I、III、IV 正确。选择 D。 10.如果一个环具有 n 个顶点则该环含有 棵生成树。 A. n² B. n C. n - 1 D. 1 10.【参考答案】 B 【解析】 生成树是不含有环的即本题情境下删去环中的任意一条边即可变成一棵生成树。且环中有 n 个顶点故有 n 条边可选择因此可以生成 n 种生成树。 11.无向图 G (V,E)|V| n|E| e且图 G 是森林。那么该图 G 中必有 棵树。 A. n B. e C. n - e D. 1 11.【参考答案】 C 【解析】 (核心将森林转化成一棵树的思想) 假设该森林中有 x 棵树。具有 n 个顶点的树有 n - 1 条边。将每一棵树连接到一个新增的结点则变成了另一棵树此时森林中的所有树变成了一棵新树且顶点数是 n 1边数是 e x由树的顶点和边的关系可知树的顶点数等于边数加一所以有 n 1 e x 1可解得 x n - e。选择 C。 12.设无向图的顶点个数为 n则该图最多有 条边。 A. n - 1 B. n (n - 1)/2 C. n (n 1)/2 D. 0 12.【参考答案】 B 【解析】 完全图为该图含有最多条边的情况。即每个顶点都和其余 n - 1 个顶点都有边相连。 13.含有 n 个顶点的完全有向图的边数为 。 A. n² B. n (n 1) C. n/2 D. n (n - 1) 13.【参考答案】 D 【解析】 有向图的完全图是任意两个顶点之间都有两条方向相反的边相连。因此可得答案 D。相比较而言无向完全图的边数则是比有向完全图的边数少一半。 14.一个有 n 个结点的无向图最少有 个连通分量最多有 。 A. 0 B. 1 C. n - 1 D. n 14.【参考答案】 BD 【解析】 图的极大连通子图称为图的连通分量。当 n 个顶点两两之间都是连通的即有路径则此时只具有 1 个连通分量属于最少的情况。当 n 个顶点各自独立不存在边则此时有 n 个连通分量属于最多的情况。综上选择 BD。 15.在一个无向图中所有顶点的度数之和等于所有边数的 倍在一个有向图中所有顶点的入度之和等于所有顶点出度之和的 倍。 A. 1/2 B. 2 C. 1 D. 4 15.【参考答案】 BC 【解析】 在无向图中每一条边两端各有一个顶点且这两个顶点的度均算了一次。因此所有顶点的度数之和等于所有边数的两倍。在有向图中一条边的两端仍然各有一个顶点该边为两端顶点贡献了一单位的入度和一单位的出度 且总是成对出现。因此有向图所有顶点的入度必然等于所有顶点的出度。综上选择 BC。 16.若一有向图有 6 个顶点11 条边问该图是稠密图还是稀疏图 A. 稠密图 B. 稀疏图 C. 都是 D. 都不是 16.【参考答案】 B 【解析】 根据稠密图和稀疏图判断公式|E|11 小于 |V|log₂|V| 6×log₂6 ≈ 15.51所以该 图为稀疏图。 17.下列有关图的定义错误的是 。 A. 无向图的所有顶点数之和可能不是边数的两倍 B. 若存在一个含有 n 个顶点且边数最小值大于 n - 2 的图那么该图一定含有环 C. 有向图所有顶点的入度与出度之和相等并且等于边数 D. 如果从 u 到 v 根本不存在路径则可记该距离为无穷 17.【参考答案】 B 【解析】 A 正确只有一个顶点没有边的无向图为此特例。B 错误首先没有说明是无向图还是有向图。其次对于无向图有大于 n - 1 条的边数才能保证该无向图有环。C、D 正确。对于 D 选项可能有点误导性考生需要根据具体题目所给含义进行判断不一定每一次都是用无穷表示不存在路径。 18.无向图 G 是一个包含 nn≥2 且 n 为偶数个顶点的图此图中有且仅有两个连通分量且每个连通分量也可看作一个完全图则图 G 中最少包含几条边 18.【参考答案】 (n2−2n)/4。设两个连通分量的顶点数分别为a、b有abn。因每个连通分量都是完全图所以两个连通分量共有a(a−1)/2b(b−1)/2条边。a(a−1)/2b(b−1)/2[(ab)2−(ab)−2ab]/2(n2−n)/2−ab。由基本不等式可知最少有(n2−n)/2−(n2/4)(n2−2n)/4条边。 19.(1) 若 G₁是一个具有 n 个顶点的连通无向图则 G₁最多有多少条边G₁最少有多少条边 (2) 若 G₂是一个具有 n 个顶点的强连通有向图则 G₂最多有多少条边G₂最少有多少条边 (3) 若 G₃是一个具有 n 个顶点的弱连通有向图则 G₃最多有多少条边G₃最少有多少条边 (说明弱连通有向图指把有向图看作无向图时仍是连通的) 19.【参考答案】 (1) 答案最多n(n−1)/2最少n−1。当该连通无向图同时又是完全图时具有最多的边共n(n−1)/2条边。当该连通无向图正好是一棵树时即不存在回路此时具有最少的边共n−1条边。注意连通无向图最少边数的情况不是刚好成环的情况因为是无向图所以不需要成环就可以是连通图了。 (2) 答案最多n(n−1)最少n。当图G2又刚好是完全图时此时具有最多的边共n(n−1)条边。当图G2刚好成环时此时具有最少的边共n条边。 (3) 答案最多n(n−1)最少n−1。当图G3刚好是完全图时具有最多的边共n(n−1)条边。当图G3正好是一棵 “有向树” 时此时具有最少的边且刚好满足弱连通图的定义共有n−1条边。 6.1.4 真题演练 20.【2009】下列关于无向连通图特性的叙述中正确的是 。 I. 所有顶点的度之和为偶数 II. 边数大于顶点个数减 1 III. 至少有一个顶点的度为 1 A. 只有 I B. 只有 II C. I 和 II D. I 和 III 20.【参考答案】 A 【解析】 Ⅰ 对无向图中所有顶点的度之和恰好为边数的 2 倍。Ⅱ 错当无向连通图为生成树的时候边数刚好等于顶点数 - 1。Ⅲ 错若无向连通图为一个环此时所有顶点的度均不为 1。 21.【2010】若无向图 G (V, E) 中含有 7 个顶点要保证图 G 在任何情况下都是连通的则需要的边数最少是 。 A. 6 B. 15 C. 16 D. 21 21.【参考答案】 C 【解析】 关键词 “任何情况下”、“连通”。若没有边数最少的限制对于 “任何情况下都要连通” 的要求很容易会联想到完全图。但本题是有 “边数最少” 的限制可以在 6 个顶点是完全图的条件下再加一条边即可满足题意。即6(6−1)/215答案为15116选 C。 说明可能有考生会认为只要满足图是 “生成树” 即可因此要选择 A。生成树确实是连通的不过该图不一定在任何情况下都是一棵生成树。 22.【2017】已知无向图 G 含有 16 条边其中度为 4 的顶点个数为 3度为 3 的顶点个数为 4其他顶点的度均小于 3。图 G 所含的顶点个数至少是 。 A. 10 B. 11 C. 13 D. 15 22.【参考答案】 B 【解析】 本题的关键是“无向图边数的 2 倍等于所有顶点的度之和。”且题目要求 “顶点个数至少是”。因此令度小于 3 的顶点有x个即度为 2 的顶点有x个由题意得16×24×33×42x解得x4。因此G的顶点个数至少为34411个。 提示若本题假设其余顶点的度均为 2 不可以解得整数的话那么可以考虑假设其余顶点的度均为 1。一般而言这两者是可以解出正确答案的若出现有度为 1也有度为 2 的顶点则题目需要增加额外信息。
