大学数据结构《图》复习课件

DATASTRUCTURE数据结构《图》期末复习精讲概念·存储·遍历·算法·应用期末冲刺2026年复习导览01图的基本概念顶点、边、度与连通性基础02图的存储结构邻接矩阵与邻接表对比03图的遍历深度优先与广度优先机制04最小生成树Prim与Kruskal贪心思想05最短路径Dijkstra与Floyd求解方法06拓扑排序与关键路径工程应用综合运用图论基础图的基本概念图是顶点与边的集合从术语定义出发，打好图论基础01图的定义与组成图由顶点集与边集构成，是描述对象间关系的数学模型图=顶点+边，记作

G=(V,E)顶点集V与边集E共同构成图结构，用方向性区分两种基本类型。集集合构成顶点图中的数据元素，代表一个对象边连接两个顶点，代表对象之间的联系记号G=(V,E)点顶点定义图中的数据元素含义代表一个对象边边作用连接两个顶点含义代表对象之间的联系向方向性无向边无方向，圆括号表示无序对有向边有方向，尖括号表示有序对度与握手定理顶点度数与边数之间存在严格的数学约束度与边数之间由握手定理建立严格的数学约束度的定义顶点度度是与某顶点相关联的边的数目。有向图中度分为入度与出度：入度是以该顶点为终点的边数，出度是以该顶点为起点的边数。握手定理与推论握手定理：无向图中所有顶点的度数之和等于边数的两倍。有向图中所有顶点的入度之和等于出度之和，均等于边数。完全图是任意两顶点间都存在边的无向图，含

n

个顶点的完全图边数为

n(n-1)/2。度为奇数的顶点个数必为偶数。路径回路与连通性路径描述顶点间的可达关系，连通性刻画图的整体结构路径与回路、连通性与连通分量共同刻画图的整体结构与顶点间可达关系。路径与回路路径是顶点序列中相邻顶点之间均有边相连。简单路径要求顶点不重复出现。回路是起点与终点相同的路径。生成树是连通图的极小连通子图。连通性无向图中若任意两顶点间都存在路径，则称该图为连通图。连通分量是无向图的极大连通子图。有向图中任意两顶点间双向可达，则称该图为强连通图。强连通分量是有向图的极大强连通子图。图的分类与子图按边密度与结构特征，图可划分为多种类型区分图类型，按结构选算法图的类型稀疏图/稠密图稀疏图的边数远小于完全图，稠密图的边数接近完全图二分图顶点可划分为两个集合，边仅存在于两个集合之间网络是带权图，每条边附带表示代价或长度的权值子图与收束子图顶点集与边集均为原图对应集合的子集生成子图要求包含原图的全部顶点意义区分图的类型有助于选择合适的存储结构与算法图论基础图的存储结构存储方式决定算法效率矩阵与链表，各有适用场景02邻接矩阵存储法用二维数组刻画顶点之间的邻接关系邻接矩阵以编号为下标·矩阵元素表示边关系定义与表示规则二维数组刻画顶点间关系邻接矩阵以顶点编号为下标，用矩阵元素表示两顶点之间是否有边无向图的邻接矩阵沿主对角线对称，有向图一般不对称带权图中，有边存权值，无边存无穷大，主对角线存

0优点判断两顶点是否相邻为常数时间，便于矩阵运算局限稀疏图存储空间浪费严重，遍历邻接点开销大邻接表存储法为每个顶点建立单链表，存储其全部邻接点图示结构采用「顺序存储+链式存储」相结合的混合存储结构组织图数据结构组成顶点表顺序存储，结点存放顶点信息与指向第一个邻接点的指针边表链式存储，结点存放邻接点下标与指向下一条边的指针顶点表边表优缺点优点稀疏图节省空间，便于快速求出某顶点的所有邻接点缺点判断两顶点是否相邻需遍历链表，有向图求入度不便无向图边表结点数为边数两倍有向图则为边数邻接矩阵与邻接表对比存储结构的选择取决于图的稠密程度与操作需求对比项邻接矩阵邻接表空间复杂度与顶点数平方同阶与顶点数加边数同阶判断两点是否相邻常数时间与该顶点度相关求全部邻接点与顶点数相关与该顶点度相关求有向图入度方便不便适用图型稠密图稀疏图结构选择依据图的稠密程度与操作需求其他存储结构面向特定图的工程化存储变体掌握多种存储方式，才能灵活应对不同的算法需求表十字链表融合邻接表与逆邻接表便利便于同时求出出度与入度有向图表邻接多重表用途用于无向图的链式存储特点每条边只存储一次无向图边边集数组单位以边为单位存储起点、终点与权值契合适合Kruskal

算法Kruskal结构选择应依据图的稠密程度与所用算法的操作特点。图论基础图的遍历一次访问，不重不漏深度与广度，两种探索路径03深度优先搜索从起点出发沿一条路径尽可能深入，无路可走再回退深度优先搜索——优先向深处探索，走不通时回溯图的遍历深度优先搜索的核心概念与实现复杂度对比优先向深处探索，走不通时回溯图的遍历从某顶点出发，沿边访问全部顶点且每个顶点仅访问一次访问标志数组避免顶点被重复访问实现方式递归实现简洁，也可借助栈模拟递归过程邻接矩阵顶点数的平方O(V²)邻接表顶点数加边数O(V+E)广度优先搜索以起点为中心层层向外扩散访问广度优先BFS按层扩展先访问起点的全部邻接点，再依次向外扩展，借助队列与访问标志数组按层推进。核心思想3项层次扩散先访问起点的全部邻接点，再依次向外扩展队列机制顶点按访问顺序入队与出队访问标志数组避免重复访问复复杂度对比邻接矩阵时间复杂度为顶点数的平方邻接表时间复杂度为顶点数加边数广度优先可按层次刻画顶点到起点的距离深度与广度优先对比两种遍历机制不同，适用场景各有侧重对比项深度优先搜索广度优先搜索辅助结构栈或递归队列访问顺序纵深优先层次优先空间开销与深度相关与宽度相关邻接表复杂度顶点数加边数顶点数加边数典型用途连通性、回路判定无权图最短路径遍历的典型应用遍历是众多图算法的通用框架以遍历为线索，贯通连通性判定、路径搜索与后续图算法连通性应用判断连通性一次遍历能够到达的顶点构成一个连通分量求连通分量个数反复从未被访问的顶点出发重新遍历判断有向图回路结合遍历与回溯状态标记路径与结构应用无权图最短路径广度优先按层次递进，首次到达即最短生成树与生成森林遍历经过的边自然构成连通子图算法共同基础遍历是最小生成树与最短路径等算法的通用框架图论算法最小生成树以最小代价连通全图贪心策略下的最优连通方案04生成树与最小生成树连通图的最小代价生成问题生成树包含全部顶点、恰好

n-1条边的极小连通子图最小生成树带权连通图中边权值之和最小的生成树按贪心策略逐步选边，以最低代价连通全部顶点，即得最小生成树要关键要点不唯一一个连通图的生成树通常不唯一唯一性权值互不相同时，最小生成树唯一应用以最低成本连通若干地点，如铺设线路、架设网络思想贪心策略：每一步都选择当前最优的边贪心策略Prim算法从单个顶点出发，逐步扩展生成树以最小权边逐次并入新顶点，直至连通全部顶点01Prim算法核心从任一顶点开始，每次选择连接树内与树外顶点的最小权边，将新顶点并入树中02扩展直至完成顶点集逐步扩大，直至包含全部顶点为止复杂度特征时间复杂度与顶点数的平方同阶与边数无关适用图型适合顶点较少、边较稠密的图Kruskal算法按权值从小到大选边，避免成环核心思路：每次选择权值最小的边，在不构成回路的前提下逐步构建最小生成树。算法步骤1排序选边将所有边按权值升序排列，依次选取2回路判断若加入后不构成回路则保留，否则舍弃3终止条件直到选中n−1条边为止复杂度与适用场景适用场景贪心策略最小生成树时间复杂度与边数

×

边数的对数同阶，与边数相关适用图型适合边相对稀疏的图并查集判断是否成环可借助并查集高效实现Prim与Kruskal对比两种算法殊途同归，选择依据图稠密程度对比项Prim算法Kruskal算法出发点从顶点出发从边出发扩展方式扩展顶点集合合并连通分量复杂度依据与顶点数相关与边数相关适用图型稠密图稀疏图关键辅助最小代价数组并查集选择依据稠密图选Prim、稀疏图选Kruskal最短路径最短路径寻找代价最小的通路单源与多源，两类经典求解05最短路径问题概述求顶点之间权值之和最小的路径核心是求两顶点间边权之和最小的路径问题定义与分类3项最短路径带权图中两顶点之间边权之和最小的路径单源最短路径求一个起点到其余全部顶点的最短路径多源最短路径求任意两个顶点之间的最短路径单源多源前提与应用4项权值非负部分经典算法的必要前提典型应用导航寻路、网络路由与地图规划导航路由规划Dijkstra算法按路径长度递增顺序逐个确定最短路径贪心策略：每次选距离最小的顶点并入已确定集合，逐步逼近全局最短路径1步骤01选取选距离最小从未确定顶点中选出距离最小的一个并入已确定集合2步骤02记录记录当前最短借助辅助数组记录源点到各顶点的当前最短距离3步骤03更新更新邻接点以新确定顶点为中介更新邻接点距离限制与复杂度3项权值非负要求所有边的权值非负时间复杂度邻接矩阵实现，与顶点数平方同阶负权边限制不能正确处理含负权边的图Floyd算法动态规划思想求解任意两点间最短路径以动态规划思想求解任意两点间最短路径，一次计算即可得到全部顶点对的最短距离。核心机制2项中转迭代逐步允许经过中间顶点，反复迭代更新两点之间的距离三重循环依次考察每个顶点作为中转点中转迭代三重循环算法特性4项复杂度时间与顶点数立方同阶，空间与顶点数平方同阶负权限制可处理带负权边的图，但不能含负权回路多源优势一次计算即可得到任意两点之间的最短路径适用场景实现简洁，适合顶点规模较小的稠密图O(V³)负权多源最短路径算法对比两种算法覆盖不同求解范围与约束条件对比项Dijkstra算法Floyd算法问题范围单源多源核心思想贪心动态规划复杂度依据与顶点数平方相关与顶点数立方相关负权边支持不支持支持适合场景单源稠密图多源小规模图图论应用拓扑排序与关键路径有向无环图上的工程智慧从排序到调度，算法落地应用06AOV网与拓扑排序用有向无环图刻画活动之间的先后约束以顶点表示活动、以有向边表示活动之间的先后关系，构成AOV网。拓扑排序将全部顶点排成线性序列核心定义AOV网以顶点表示活动，以有向边表示活动之间的先后关系拓扑排序将AOV网中所有顶点排成线性序列，使每条边的前驱都排在后继之前质关键性质与应用序列拓扑序列通常

不唯一应用应用场景包括课程安排、任务调度与编译依赖处理回路存在回路的有向图无法进行拓扑排序检测拓扑排序可用于检测有向图中是否存在回路不唯一有回路不可排用于检测回路拓扑排序的实现反复输出入度为零的顶点并删除其出边“反复输出入度为零的顶点并删除其出边，即可得到一种可行拓扑序列。”“入度归零逐个取，回路到头现原形”第1步初始化统计入度统计各顶点入度，将入度为零者入栈或入队。第2步输出顶点取出并输出每次取出一个顶点输出，并将其所有邻接点的入度减一。第3步收入集合入度归零入列若某邻接点入度减后为零，则将其加入待处理集合。第4步检测回路回路判断若最终输出顶点数少于顶点总数，说明图中存在回路。关键结论邻接表时间复杂度为顶点数加边数栈与队列均可实现，得到的拓扑序列可能不同AOE网与关键路径概念用边表示活动及其持续时间，寻找决定总工期的路径用边表示活动及其持续时间，关键路径决定工程总工期核心概念3项AOE网以顶点表示事件，以有向边表示活动及其持续时间关键路径从源点到汇点路径长度最长的路径关键活动位于关键路径上的活动，其延误会直接影响总工期期工期影响决定最短工期关键路径的长度决定整个工程的最短完成时间缩短关键活动只有缩短关键活动的时间才可能缩短整个工期可能不唯一关键路径可能不唯一，需综合判断关键路径的求解四个时间量的递推计算锁定关键活动工期规划的核心在于先