高中信息技术选择性必修1 数据与数据结构 图的基本概念知识清单

高中信息技术选择性必修1数据与数据结构图的基本概念知识清单一、课程导学：从现实关系到数据结构的思维跃迁在完成了线性表（如队列、栈）和树形结构的学习后，我们迎来了数据结构中最为灵活、最为复杂的逻辑结构——图。本章节“图的基本概念”是开启第四章学习的基石，其核心在于理解“多对多”的非线性逻辑关系。这不仅是知识点的更新，更是一次思维方式的跃迁：从关注数据元素的前驱后继（一对一），到关注数据的层级隶属（一对多），最终到关注数据间的任意关联（多对多）。本清单将严格按照高中信息技术课程标准（2017版2020年修订）的要求，深度剖析粤教版选择性必修1第四章4.1节的核心内容，结合学业水平考试与高考选考（如适用）的考情，为你构建一个严谨、系统、无死角的图论基础知识体系。二、【核心概念精讲】——基础中的基础（★基础）（一）图的定义与数学表示（【基础】）1、定义：图（Graph）是一种非线性数据结构，它是由顶点的有限非空集合和顶点之间边的集合组成。通常表示为：G=(V,E)。其中，G表示一个图，V（Vertex）是图G中顶点的集合，E（Edge）是图G中顶点之间边的集合。2、关键特性：①顶点集合V不能为空。即一个图至少包含一个顶点。②边集合E可以为空。即允许存在只有顶点而没有边的图，这样的图称为零图。③对比与记忆：线性表（如链表）允许空表，树允许空树，但图在定义上不允许顶点集为空，这是图结构的一个基本约束。3、术语解析：①阶（Order）：图G中顶点的个数，通常用|V|表示。例如，一个图有5个顶点，则称该图为5阶图。②边（Edge）：顶点之间的逻辑关系。根据边是否有方向，图分为有向图和无向图。③端点（Endpoint）：一条边所连接的两个顶点。（二）图的分类：有向图与无向图（【高频考点】）1、无向图（UndirectedGraph）：①定义：若图G中的每条边都是无方向的，即(v,w)等价于(w,v)，则称G为无向图。②边的表示：用圆括号表示，如(v,w)。顶点v和w互为邻接点，称边(v,w)依附于顶点v和w，或者说边与顶点相关联。③实例分析：在社交软件中，如果用户之间的关系是“好友”，这种关系是双向的，A是B的好友，B也必然是A的好友，这种关系模型就可以用无向图来描述。2、有向图（DirectedGraph/Digraph）：①定义：若图G中的每条边都是有方向的，即<v,w>与<w,v>不同，则称G为有向图。②边的表示：用尖括号表示，如<v,w>。其中v称为弧尾（Tail）或初始点，w称为弧头（Head）或终端点。此时，我们称顶点v邻接到w，或顶点w邻接自v。③实例分析：微博中的“关注”关系就是典型的有向图。A关注了B，并不代表B关注了A。3、辨析考点：判断实际问题中应构建为有向图还是无向图，是学业水平考试中常见的应用题。关键在于分析关系是否具有双向性。（三）图的分类：简单图与多重图（【基础】【易错点】）1、简单图（SimpleGraph）：①定义：在数据结构课程（如粤教版选择性必修1）的默认语境下，如无特殊说明，我们讨论的图通常指简单图。简单图必须满足两个条件：第一，不存在重复边。即图中任意两个顶点之间最多只有一条边。第二，不存在自环（Loop）。即不存在顶点连接到自身的边。②重要性：简单图是算法分析与设计的基准模型，后续学习的图的遍历（DFS/BFS）、最小生成树（Prim/Kruskal）、最短路径（Dijkstra/Floyd）等算法，大多基于简单图进行讨论。2、多重图（Multigraph）：①定义：与简单图相对，允许在两个顶点之间存在多条相同的边（称为平行边或重边），或者存在顶点到自身的边（自环）的图，称为多重图。②现实意义：例如在航空网络中，两个城市之间可能有多条不同的航线（由不同航空公司执飞，或不同时间段），这种关系就需要用多重图来建模。（四）完全图（【重要】【热点】）完全图是边数达到最大值的图，是考试中计算边数范围的基础。1、无向完全图：①定义：在无向图中，如果任意两个顶点之间都存在且仅存在一条边，则该图称为无向完全图。②边数计算：含有n个顶点的无向完全图，其边数为C(n,2)=n(n1)/2。③实例：3个顶点的无向完全图，应有3(31)/2=3条边，构成一个三角形。2、有向完全图：①定义：在有向图中，如果任意两个顶点之间都存在且仅存在方向相反的两条弧（即互为邻接），则该图称为有向完全图。②边数计算：含有n个顶点的有向完全图，其弧数为n(n1)。③实例：3个顶点的有向完全图，应有3(31)=6条边，即每两个点之间都有两个方向的箭头。三、【顶点的结构特征】——度与度数定理（▲▲▲）（一）度的定义1、无向图的度（Degree）：①定义：顶点v的度是指依附于该顶点的边的条数，记为TD(v)（或D(v)）。②观察：在无向图中，每一条边都会为其所依附的两个顶点各贡献1度。2、有向图的度：①入度（InDegree）：以顶点v为终点的有向边的数目，记为ID(v)。即有多少条边指向v。②出度（OutDegree）：以顶点v为起点的有向边的数目，记为OD(v)。即从v出发有多少条边。③总度：顶点v的度等于其入度与出度之和，即TD(v)=ID(v)+OD(v)。（二）【高频考点】握手定理（HandshakingLemma）这是图论中最重要的基本定理之一，也是各类考试计算题的核心依据。1、定理内容：在任何图（无向图）中，所有顶点的度数之和等于边数的两倍。即：∑v∈VTD(v)=2∣E∣\sum_{v\inV}TD(v)=2|E|v∈V∑​TD(v)=2∣E∣对于有向图，所有顶点的入度之和等于所有顶点的出度之和，等于边数（弧数）|E|。即：∑v∈VID(v)=∑v∈VOD(v)=∣E∣\sum_{v\inV}ID(v)=\sum_{v\inV}OD(v)=|E|v∈V∑​ID(v)=v∈V∑​OD(v)=∣E∣2、推论及应用：①推论1：在任意图中，度数为奇数的顶点个数必为偶数。②应用：已知图中各顶点的度数，可以反推图中边的数量；或者验证所给度数序列是否能构成一个图（图的可图化问题基础）。四、【图的全局特征】——连通性探析（▲▲▲）（一）路径与回路（【基础】）...路径（Path）：在图G中，从顶点vp到顶点vq的一条路径是一个顶点序列vp,vi1,vi2,...,vim,vq，且序列中每两个相邻顶点都构成图G中的一条边。2、路径长度（PathLength）：路径上经过的边的数目。3、简单路径（SimplePath）：序列中顶点不重复出现的路径。4、回路（Cycle）/环（Loop）：第一个顶点和最后一个顶点相同的路径。如果一个图有n个顶点，并且边数大于n1，则此图一定有环（在连通图的前提下）。（二）连通性核心概念（▲▲▲【高频考点】）1、无向图的连通性：①连通：在无向图中，若从顶点v到顶点w存在路径，则称v和w是连通的。②连通图（ConnectedGraph）：若图G中任意两个顶点都是连通的，则称图G为连通图。否则称为非连通图。③【难点】连通分量（Connectedponent）：无向图中的极大连通子图称为连通分量。第一，“极大”的含义：包含尽可能多的顶点（即依附于这些顶点的所有边也必须包含在内）。第二，任何连通图的连通分量只有一个，即其自身；而非连通图则有多个连通分量。第三，判断技巧：一个孤立顶点也是一个连通分量（因为它自身是连通的，且无法再扩大）。2、有向图的连通性：①强连通：在有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的。②强连通图（StronglyConnectedGraph）：若图中任何一对顶点都是强连通的，则称此图为强连通图。③强连通分量（StronglyConnectedponent）：有向图中的极大强连通子图称为其强连通分量。④实例：一个有向完全图一定是强连通图。（三）距离（【基础】）1、定义：从顶点u出发到顶点v的最短路径（若存在）的长度，称为从u到v的距离。2、特殊规定：若从u到v根本不存在路径，则记该距离为无穷大（∞）。五、【图的扩展概念】——网与稀疏性（一）网（Network）——带权图（【重要】）1、定义：在一个图中，每条边（或弧）上标上具有某种含义的数值，该数值称为该边的权（Weight）。这种边上带有权值的图称为带权图（WeightedGraph），也常被称为网。2、权的含义：权可以代表实际应用中的多种含义，如：①交通网络：距离、通行时间、路费。②通信网络：带宽、延迟、成本。③工程调度：任务持续时间、资源消耗。3、学习意义：引入了“权”的概念后，对图的研究就从单纯的连通性问题，转向了最优化问题，如求最短路径（Dijkstra算法）、求最小生成树（Prim算法）等。（二）稠密图与稀疏图（【了解】）1、定义：这是对图边数多少的一种定性描述。①稀疏图（SparseGraph）：边数很少的图。一般认为，当图G满足|E|<|V|log|V|时，可以将G视为稀疏图。②稠密图（DenseGraph）：反之，边数非常多的图，接近于完全图。2、实践意义：稀疏图和稠密图在计算机中的存储方式选择至关重要。通常，稀疏图适合用邻接表存储以节省空间，稠密图适合用邻接矩阵存储以便快速访问。六、【知识辨析与思维拓展】（一）图与树的关系（【难点】）1、树是图的特例：树是一种特殊的图。具体来说，树是无环连通无向图。2、特征对比：①一个有n个顶点的树，必然有且仅有n1条边。②在树中，任意两个顶点之间有且仅有一条简单路径。③如果一个连通图的边数大于n1，则它一定存在环，此时就不能称为树了。3、有向树（DirectedTree）：一个顶点的入度为0（根），其余顶点的入度均为1的有向图，称为有向树。（二）图与生活建模将现实问题抽象为图模型是信息技术核心素养“计算思维”的重要体现。例如：1、地铁线路图：站点为顶点，站点间的直达线路为边（通常是无向加权图，权为时间或距离）。2、互联网超链接：网页为顶点，超链接为有向边。3、化学分子结构：原子为顶点，化学键为边。七、【考点、考向与解题策略】（▲▲▲【高频考点】）本小节在学业水平考试及高考选考中，通常以选择题、填空题和综合应用题的第一问出现。分值占比虽不大，但却是后续解题的基础。（一）常见题型与考查方式1、概念辨析题：①考向：判断给定描述对应的是有向图还是无向图，是简单图还是多重图。②真题模拟：例：在表示微信朋友圈的好友关系时，最适宜采用的数据结构是（）A.有向图B.无向图C.树D.队列。答案：B（因为好友关系是双向的）。2、度数计算题：①考向：利用握手定理进行计算。②真题模拟：例：设一个无向图有8个顶点，每个顶点的度数均为3，则该图共有多少条边？解题步骤：根据握手定理，总度数之和=83=24。又因为总度数之和=2|E|，所以|E|=24/2=12条边。③易错点：忘记除以2，直接拿总度数当边数。3、完全图边数计算题：①考向：直接考查公式。②真题模拟：例：一个6个顶点的有向完全图，共有多少条弧？解题步骤：直接套用公式n(n1)=65=30条。4、连通分量判断题：①考向：给定一个非连通图，要求数出有几个连通分量（或强连通分量）。②解题要点：在无向图中，从一个未被访问过的顶点出发进行遍历（深度优先或广度优先），能遍历到的所有顶点构成一个连通分量。重复此过程直到所有顶点都被访问，遍历的次数即为连通分量的个数。（二）解答要点与易错点归纳1、审题要清：题目中说的是“有向”还是“无向”？是“完全图”还是“连通图”？是完全不同的概念。2、理解“极大”：连通分量是“极大”连通子图，意味着不仅要包含尽可能多的顶点，还要包含这些顶点之间所有的边。单独的顶点如果没有边相连，也是分量。3、空图问题：牢记图不允许顶点集为空，但边集可为空。4、符号规范：做题时建议规范使用<>表示有向边，()表示无向边，养成良好习惯。八、【综合素养提升】——从概念到应用作为代表最高水平的课程，本章的学习不能仅停留在记忆定义的层面。我们必须建立宏观的知识视角：1、建立知识图谱：将本节概念与后续章节（图的存储