盲校高中信息技术选择性必修1《图的基本概念》知识清单

盲校高中信息技术选择性必修1《图的基本概念》知识清单一、课程导引：从多元视角理解图论的起源与价值（一）【基础】图论的起源：从哥尼斯堡七桥问题说起十八世纪的哥尼斯堡城，普雷格尔河穿城而过，河中心有两个岛屿，七座桥梁连接着两岸与岛屿。一个有趣的散步问题困扰着居民：是否可以从某处出发，恰好每座桥走一次，既不重复也不遗漏，最后回到起点？这个问题看似简单，却蕴含了深刻的数学原理。1736年，瑞士数学家欧拉（LeonhardEuler）创造性地将陆地抽象为点，桥梁抽象为连接点的线，从而将七桥问题转化为一个“一笔画”问题。他证明了，对于一个连通图，如果存在一条路径，能够不重复地遍历每一条边，这样的路径称为欧拉路径；如果这条路径还能回到起点，则称为欧拉回路。而一个图存在欧拉回路的充要条件是所有顶点的度数均为偶数。七桥问题所对应的图，四个顶点的度数均为奇数，因此不存在这样的走法。欧拉的工作不仅解决了七桥问题，更开创了数学的一个新分支——图论。这一经典案例揭示了图论的核心思想：忽略事物的非本质属性，将其抽象为点和线构成的图，通过研究图的结构和性质来解决实际问题，这正是计算思维中“抽象”与“建模”思想的生动体现。（二）【重要】图在信息时代的多维应用图景图作为一种强大的非线性数据结构，在现实世界和信息技术领域有着极其广泛的应用。理解其应用场景，有助于我们深刻领会学习本章的价值。1.社交网络分析：在微信、微博等社交平台中，每个用户可以抽象为一个顶点，用户之间的“关注”、“好友”关系则可以抽象为一条边。由此构成的“社交图”是好友推荐、信息流推送、舆情分析、社区发现等功能的核心数据结构。例如，通过分析图中顶点的度（好友数量）可以识别“意见领袖”；通过寻找图中的连通分量可以划分不同的兴趣群体。2.交通导航与路径规划：高德地图、百度地图等导航软件的核心功能，如最短路径规划、实时路况分析、公交地铁路线查询，其底层支撑正是图论算法。将路口抽象为顶点，道路抽象为带权值的边（权值可以是距离、通行时间、路况拥堵指数等），导航问题就转化为在带权图中求解最短路径的问题（如Dijkstra算法）。3.计算机网络与通信：互联网本身就是一个巨大的图，路由器是顶点，光缆、网线是边。路由协议（如OSPF，开放最短路径优先协议）的核心就是通过图论算法动态计算网络中数据包传输的最优路径。局域网拓扑结构（星型、总线型、环型）也是图的具体表现形式。4.推荐系统：电商平台的“买了该商品的用户还买了……”功能，背后隐含着“用户商品”二部图模型。通过分析用户与商品之间的连接关系，可以挖掘用户兴趣和商品关联性，从而实现精准推荐。5.软件工程：在软件开发中，程序模块之间的调用关系可以用“函数调用图”来表示，有助于理解系统结构、进行逆向工程。大型软件的编译过程，也需要根据文件之间的依赖关系图，确定编译的先后顺序（拓扑排序）。二、【核心概念】图的定义、分类与基本术语（一）【基础】图的定义与数学表示图（Graph）是一种比线性表和树更为复杂的非线性数据结构。线性表中，数据元素之间仅存在“一对一”的线性关系；树结构中，节点之间存在“一对多”的层次关系；而在图结构中，节点之间的关系是任意的，任意两个数据元素之间都可能存在“多对多”的关系。一个图G是由两个集合构成的二元组，记作G=(V,E)。1.V(Ver)：顶点集，是图G中所有顶点的非空有限集合。V中的每个元素称为一个顶点（Vertex）或节点（Node）。通常用|V|表示图中顶点的个数，称为图的阶（Order）。2.E(EdgeSet)：边集，是图G中所有边的有限集合。E中的每个元素称为一条边（Edge）或弧（Arc）。边是连接两个顶点的关系。通常用|E|表示图中边的条数。（二）【基础】图的基本分类与辨析根据边是否有方向、是否带权值、是否存在重复边等属性，图可以被划分为多种类型，这是理解后续算法的基础。1.【重要】有向图vs.无向图1.无向图（UndirectedGraph）：图中的边没有方向，用无序对(v,w)表示。若顶点v和w之间存在一条无向边，则称v和w互为邻接点，边(v,w)依附于v和w。例如，微信好友关系就是一个典型的无向图，若A是B的好友，则B也必然是A的好友。2.有向图（DirectedGraph或Digraph）：图中的边有方向，用有序对<v,w>表示，称为弧（Arc）。v称为弧尾（Tail）或初始点，w称为弧头（Head）或终端点。边<v,w>表示从v指向w，与从w指向v的边<w,v>是不同的。例如，微博的关注关系就是有向图，A关注B，并不意味着B也关注A。1.【基础】稀疏图vs.稠密图1.这是一个相对的概念，通常根据边数|E|相对于顶点数|V|的数量级来划分。如果一个图的边数远小于其完全图（任意两个顶点之间都有边）的边数，则称为稀疏图（SparseGraph），通常认为|E|<|V|log|V|。反之，如果边数接近完全图的边数，则称为稠密图（DenseGraph）。1.【基础】带权图（网）图的边或弧上，常常附带一个数值，用以表示该边或弧的某种属性，如距离、时间、成本、流量等，这个数值被称为权（Weight）。这种边上带有权值的图，称为带权图（WeightedGraph），有时也称之为网（Network）。导航软件中的路况图就是典型的带权图。2.【基础】其他重要图类型1.完全图（pleteGraph）：在无向图中，任意两个顶点之间都存在一条边的图。一个具有n个顶点的无向完全图，其边数为n(n1)/2。2.连通图（ConnectedGraph）：在无向图中，如果从任一顶点到另一顶点都存在路径，则称该图为连通图。3.强连通图（StronglyConnectedGraph）：在有向图中，如果从任一顶点到另一顶点都存在路径，则称该图为强连通图。4.子图（Subgraph）：设有两个图G=(V,E)和G'=(V',E')，如果V'⊆V且E'⊆E，则称G'是G的子图。（三）【核心】图的顶点与边关系术语1.【基础】度（Degree）1.无向图中：顶点v的度是指依附于该顶点的边的条数，记作TD(v)。在无向图中，所有顶点的度数之和等于边数的两倍（因为每条边被两个顶点计算）。即∑TD(v)=2|E|。2.有向图中：顶点的度分为入度（Indegree）和出度（Outdegree）。1.3.入度：以顶点v为终点（弧头）的弧的数目，记作ID(v)。2.4.出度：以顶点v为始点（弧尾）的弧的数目，记作OD(v)。3.5.顶点v的度TD(v)=ID(v)+OD(v)。在有向图中，所有顶点的入度之和等于出度之和，也等于边数|E|。【高频考点】【★☆☆】度是描述图中顶点活跃程度或重要性的基本指标。在社交网络分析中，一个用户的度（好友数）直观反映了其社交圈的大小。考题常会给出一个图的顶点和边的关系，要求计算特定顶点的度，或者根据所有顶点的度数推断图的边数或结构。1.【难点】路径与回路1.路径（Path）：在一个图中，从顶点v到顶点w的路径是一个顶点序列，序列中相邻两个顶点之间都有边相连。路径上经过的边的数目称为路径长度（LengthofPath）。2.简单路径（SimplePath）：若一条路径上的顶点不重复出现，则称其为简单路径。3.回路/环（Cycle）：若一条路径的第一个顶点和最后一个顶点相同，则称其为回路或环。4.简单回路（SimpleCycle）：除第一个和最后一个顶点相同外，其余顶点均不重复的回路。【高频考点】【★★☆】判断路径是否存在、寻找最短路径（第四章后续内容）是图论算法的核心。识别一个图中是否存在环路，对于许多应用（如任务调度中的死锁检测、编译依赖分析）至关重要。1.【基础】连通分量与强连通分量1.无向图的连通分量（Connectedponent）：极大连通子图。即在该子图中，任意两个顶点之间都是连通的，且再加入原图中的任何一个其他顶点，该子图就不再连通。一个非连通图由若干个连通分量构成。2.有向图的强连通分量（StronglyConnectedponent,SCC）：极大强连通子图。即在该子图中，任意两个顶点之间都是相互可达的（即从v到w和从w到v都存在路径）。有向图的强连通分量是其结构分析的关键。【重要】【★★☆】理解连通分量有助于从整体上把握图的结构。例如，在分析一个交通网络图时，其连通分量代表了一个个无法通过陆路交通相互到达的孤立区域。而强连通分量在有向图分析（如程序的控制流图、Web网页链接分析）中极为重要。三、【核心技能】图的存储结构：计算机如何“理解”图要在计算机中处理和操作图，首先必须解决如何将图的顶点和边的信息有效地存储起来。根据图的结构特点和操作需求，我们主要学习两种最基础的存储结构：邻接矩阵和邻接表。（一）【基础】【高频考点】邻接矩阵（AdjacencyMatrix）邻接矩阵是图的一种顺序存储结构，其核心思想是利用一维数组存储顶点信息，利用二维数组（矩阵）存储顶点之间的邻接关系。1.表示方法0...n数组：用一个一维数组vexs[0...n1]存储图中的n个顶点信息。2.邻接矩阵：用一个n×n的二维数组edges[n][n]（或称为矩阵A）表示顶点之间的邻接关系。矩阵元素的定义规则如下：1.3.对于无权图：edges[i][j]=1，若顶点vexs[i]与vexs[j]之间存在边或弧。edges[i][j]=0，若顶点vexs[i]与vexs[j]之间不存在边或弧。2.4.对于带权图（网）：edges[i][j]=wij，若顶点vexs[i]与vexs[j]之间存在边或弧，且权值为wij。edges[i][j]=∞（或一个计算机能表示的极大值），若顶点vexs[i]与vexs[j]之间不存在边或弧。edges[i][i]通常设为0（表示顶点到自身的距离为0）。1.【非常重要】邻接矩阵的性质与特点1.对称性：对于无向图，其邻接矩阵一定是对称矩阵，即edges[i][j]=edges[j][i]。这一性质可用于压缩存储，只需存储上三角或下三角矩阵即可节省一半空间。2.唯一性：图的邻接矩阵表示是唯一的，这有利于算法的实现和图的比较。3.空间复杂度：邻接矩阵的空间复杂度为O(|V|²)，其中|V|是顶点数。无论实际边数多少，都需要申请n²个存储单元。因此，邻接矩阵更适合存储稠密图。4.度计算的便捷性：1.5.对于无向图，第i行的元素之和（或第i列的元素之和）即为顶点vexs[i]的度。2.6.对于有向图，第i行的元素之和为顶点vexs[i]的出度；第i列的元素之和为顶点vexs[i]的入度。7.判断边的存在性：判断任意两个顶点之间是否有边相连，时间复杂度为O(1)，只需检查edges[i][j]是否为1或∞即可。【高频考点】【★★★】邻接矩阵是考试中要求必须掌握的基本存储结构。考题通常会给出一个具体的图（无向/有向，无权/带权），要求画出其邻接矩阵，并根据矩阵计算各顶点的度、入度、出度，或判断图的类型。反之，也可能给出一个邻接矩阵，要求还原出图的形状。（二）【基础】【核心难点】邻接表（AdjacencyList）邻接表是图的一种链式存储结构，它结合了顺序存储和链式存储的优点，主要用于解决邻接矩阵在存储稀疏图时浪费空间的问题。1.表示方法邻接表由两部分组成：顶点表和边表。1.顶点表：一个一维数组。数组的每个元素对应一个顶点，它包含两个域：1.2.data域：存储该顶点的信息。2.3.firstedge域：是一个指针，指向该顶点的第一条边（即该顶点的第一个邻接点）所对应的边表节点。4.边表：由若干链表节点组成。每个边表节点对应一条依附于某个顶点的边，它至少包含两个域：1.5.adjvex域：存储该条边所指向的邻接点在顶点表中的下标（位置）。2.6.next域：是一个指针，指向依附于同一顶点的下一条边所对应的边表节点。3.7.（对于带权图，还需增加一个weight域来存储边的权值。）1.【非常重要】邻接表的特点与分析1.空间复杂度：对于有|V|个顶点和|E|条边的图，其邻接表表示需要的存储空间为O(|V|+|E|)。1.2.顶点表需要|V|个存储单元。2.3.边表需要|E|个存储单元（无向图每条边对应两个边表节点，需要2|E|个；有向图每条弧对应一个边表节点，需要|E|个）。3.4.因此，邻接表尤其适合存储稀疏图，可以极大地节省存储空间。5.度的计算：1.6.对于无向图，求一个顶点的度，只需遍历其对应的边表，统计节点个数即可。时间复杂度为O(e)，e为该顶点的度。2.7.对于有向图，求一个顶点的出度，只需遍历其对应的边表（称为“出边表”）。但若要求入度，则需要遍历整个邻接表（或者构建一个“逆邻接表”），这是邻接表在有向图中的一个缺点。因此，对于需要频繁计算入度的有向图，通常会同时建立邻接表和逆邻接表。8.判断边的存在性：判断顶点v和w之间是否有边，需要在v的边表中遍历查找是否存在adjvex等于w下标的节点。时间复杂度为O(d)，d为顶点v的度。在最坏情况下可能达到O(|V|)。【重要】【★★☆】邻接表与邻接矩阵的比较是数据结构课程的经典问题。需要学生从空间效率（稠密图vs稀疏图）和时间效率（判断边是否存在vs遍历顶点的所有邻接点）两个维度深刻理解两种存储结构的适用场景。在编程实现图算法时，邻接表因其空间优势和遍历邻接点的便捷性，应用更为广泛。（三）【拓展】两种存储结构的对比与选型比较维度邻接矩阵邻接表存储方式顺序存储顺序+链式存储空间复杂度O(|V|²)O(|V|+|E|)适用图类型稠密图稀疏图添加/删除顶点复杂，常需重构矩阵较容易，直接在顶点表后添加/删除添加/删除边O(1)O(d)，d为顶点的度判断边是否存在O(1)O(d)求顶点的度无向图O(1)，有向图O(|V|)无向图O(d)，有向图出度O(d)，入度需遍历全表遍历所有邻接点需扫描整行，耗时O(|V|)直接遍历边表，耗时O(d)【难点与选型指导】：在选择存储结构时，需要综合权衡。如果算法中需要频繁判断任意两个顶点之间是否存在边（例如，在Floyd算法中），邻接矩阵是首选。如果算法主要涉及遍历一个顶点的所有邻接点（例如，在DFS、BFS遍历中），且图本身是稀疏的，邻接表则更为高效。四、【基础算法】图的遍历：探索图的“地图”图的遍历是指从图中某一顶点出发，按照某种搜索策略沿着边访问图中其余顶点，且使每个顶点仅被访问一次的过程。它是许多图论算法的基础。根据搜索路径的策略不同，主要有两种遍历方式：深度优先搜索和广度优先搜索。（一）【核心】【高频考点】深度优先搜索（DepthFirstSearch,DFS）1.算法思想：类似于树的先序遍历，是一种“不撞南墙不回头”的策略。它从起始顶点v出发，首先访问v，然后选择一个与v相邻且未被访问过的顶点w进行访问。接着，再从w出发，进行类似的深度优先访问。当遇到一个所有邻接顶点都已被访问过的顶点u时，则回溯到最近一次访问过的、且尚有未被访问邻接点的顶点，重复上述过程，直至从v出发可达的所有顶点均被访问。如果图中尚有未被访问的顶点，则从中选一个作为新的起始点，重复此过程，直到所有顶点均被访问。2.算法实现要点1.标记数组：需要一个visited[]数组来记录每个顶点是否已被访问，避免重复访问和形成死循环。2.递归/栈：DFS的本质是递归过程，可以自然地用递归函数实现。递归调用的底层机制就是系统栈。也可以显式地使用一个栈来模拟递归过程。1.【非常重要】生成树与森林在DFS遍历过程中，根据访问路径所经过的边（即从已访问顶点到达未访问顶点所经过的边）构成的图，是一个无环的连通子图。对于连通图，这些边恰好构成一棵树，称为深度优先生成树（DepthFirstSearchTree）。对于非连通图，则每个连通分量都会生成一棵树，这些树组成一个深度优先生成森林。【考点剖析】1.遍历序列：给定一个图和起始点，能够模拟并写出DFS的访问顶点序列。需注意，由于邻接点的选择顺序不同（例如，按顶点编号顺序选择），得到的序列可能不唯一。2.算法应用：DFS可用于判断图的连通性、求解连通分量个数、检测图中是否存在环路等。3.时空复杂度：使用邻接表存储时，DFS的时间复杂度为O(|V|+|E|)。使用邻接矩阵存储时，需要扫描整个矩阵以查找每个顶点的所有邻接点，时间复杂度为O(|V|²)。（二）【核心】【高频考点】广度优先搜索（BreadthFirstSearch,BFS）1.算法思想：类似于树的层序遍历，是一种“层层推进”的策略。它从起始顶点v出发，首先访问v，然后依次访问v的所有未被访问过的邻接点。接着，再从这些邻接点出发，访问它们的所有未被访问过的邻接点，并保证“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。依此类推，直至从v出发可达的所有顶点均被访问。如果图中尚有未被访问的顶点，则从中选一个作为新的起始点，重复此过程。2.算法实现要点1.标记数组：同样需要visited[]数组记录访问状态。2.队列（Queue）：BFS的核心数据结构是队列，用以保证访问的层次顺序。访问一个顶点后，将其入队；当要访问下一层顶点时，从队列中取出一个顶点，并访问其所有未被访问的邻接点。1.【非常重要】生成树在BFS遍历过程中，所经过的边（连接已访问顶点与其首次发现的未访问邻接点的边）构成的图，也是一棵树，称为广度优先生成树（BreadthFirstSearchTree）。与DFS不同，BFS生成树的路径长度是从起始点到各顶点的最短路径长度（以边数计）。【考点剖析】1.遍历序列：能够模拟并写出BFS的访问顶点序列，其序列同样受邻接点选择顺序影响。2.最短路径：在无权图中，BFS首次访问到某个顶点时所经过的路径，就是从起始点到该顶点的最短路径（最少边数）。这是BFS最重要的性质之一。3.时空复杂度：与DFS相同，使用邻接表时时间复杂度为O(|V|+|E|)，使用邻接矩阵时为O(|V|²)。（三）【重要】DFS与BFS的对比与应用场景比较维度深度优先搜索(DFS)广度优先搜索(BFS)核心数据结构栈（递归本质/显式栈）队列空间复杂度O(h)，h为递归深度（或栈深）O(w)，w为最大宽度（通常远大于h）搜索策略优先深入，回溯后再扩展优先扩展，层层推进能否找到最短路径不能保证找到无权图的最短路径能保证找到无权图的最短路径主要应用拓扑排序、连通分量、环路检测、迷宫求解最短路径（无权图）、网络爬虫、广播式传播【难点与选型指导】：如果问题目标是寻找一个解是否存在（例如，在迷宫中寻找一条出路），DFS往往更合适，因为它能快速深入。如果问题是寻找最优解（例如，找出从城市A到城市B中转次数最少的路线），则在无权图中应首选BFS。五、【核心应用】图论初步：生成树与最短路径初探（一）【重要】生成树（SpanningTree）1.定义：对于一个连通图G，其生成树是一个包含G中所有顶点的极小连通子图。所谓“极小”，是指在保持图连通的前提下，边数尽可能少。2.性质：1.一个连通图的生成树包含|V|个顶点和|V|1条边。2.在生成树中，任意添加一条原图中的边，必定会形成一个回路。这个性质体现了“极小连通”的含义。3.一个连通图的生成树可能不唯一。例如，对同一个图进行DFS和BFS，会得到不同的生成树。1.最小生成树（MinimumSpanningTree,MST）【概念引入】：对于带权连通图（网），生成树各边的权值之和称为该生成树的权。使这个权值之和最小的生成树，称为最小生成树。这是图论中的一个经典优化问题，典型的求解算法有Prim算法和Kruskal算法，将在后续章节深入学习。【基础考点】给定一个连通图，能够根据DFS或BFS遍历过程，画出其对应的生成树或生成森林。理解生成树中边数与顶点数的关系。（二）【重要】最短路径（ShortestPath）初探【概念引入】1.定义：在带权图G中，给定一个起始顶点（源点）和一个终止顶点（终点），从源点到终点的所有路径中，各边权值之和最小的那条路径，称为最短路径，其长度称为最短路径长度。2.两类经典问题：1.单源最短路径：求从某个源点到图中其余各顶点的最短路径。经典算法是Dijkstra算法。2.所有顶点对之间的最短路径：求图中任意两个顶点之间的最短路径。经典算法是Floyd算法。1.与遍历的联系：BFS算法实际上就是无权图（即所有边的权值均为1）中的单源最短路径算法。理解BFS的“层次”概念，是理解Dijkstra算法“按路径长度递增次序产生最短路径”思想的基础。六、【知识整合】常见题型、解题策略与易错点剖析（一）【高频考点】概念辨析与计算题1.题型示例：1.2.一个含有n个顶点和e条边的无向图，在其邻接表表示中，边表节点的总数为（2e）。2.3.一个具有n个顶点的有向完全图，其边的数目为（n(n1)）。3.4.已知一个图的邻接矩阵如下，判断该图是有向图还是无向图？计算各顶点的度/出度/入度，并画出该图。5.解题策略：1.6.熟记图的基本术语的定义和数学关系。2.7.掌握邻接矩阵和邻接表两种存储结构的转换规则。从矩阵到图：非零元素（或非∞）即为边。从表到图：根据每个顶点的边表画出邻接关系。3.8.计算度数时，务必先分清图是有向还是无向。9.【易错点】1.10.混淆有向图和无向图的度：在有向图中，提到“度”通常需要指明是入度还是出度，或者特指二者之和。2.11.邻接矩阵的对称性误判：看到矩阵是对称的，可以判断为无向图。但看到非对称矩阵，则一定是有向图。3.12.邻接表节点数的误算：对于无向图，每条边会在两个顶点的边表中各出现一次，所以边表节点总数是2|E|。（二）【中频考点】图的遍历序列分析1.题型示例：给定一个图和指定的起始点，分别写出其DFS和BFS遍历序列（假设邻接点按编号升序访问）。2.解题策略：1.3.DFS：牢记“深入、回溯”原则。可以手动画出递归搜索的过程图。2.4.BFS：牢记“分层、队列”原则。可以用队列模拟入队出队的过程，辅助写出序列。5.【易错点】1.6.未考虑非连通图：无论是DFS还是BFS，如果图是非连通的，必须从一个新的未访问顶点开始继续遍历，直到所有顶点都被访问。2.7.BFS队列操作错误：保证“先访问的顶点先出队，其邻接点被访问”。（三）【难点】存储结构与算法效率的综合分析1.题型示例：对于一个具有1000个顶点和3000条边的稀疏图，问：(1)采用邻接矩阵和邻接表存储，各需要多少存储单元？（大致估算）(2)若需频繁执行“判断两个给定顶点之间是否有边”的操作，哪种存储结构更合适？为什么？(3)若需频繁执行“遍历某个顶点的所有邻接点”的操作，哪