《数据结构》课件 第8章 图

数据结构第八章·图从社交网络拓扑到全球交通枢纽，深入探索连接万物的逻辑本源与核心算法奥秘。课程导入与学习目标01核心概念：从理论到现实深度解析图的定义、顶点与边的关系术语体系，结合社交网络、地图导航等实际案例，理解图结构作为复杂关系模型的底层逻辑。02存储结构：数据的物理映射系统掌握邻接矩阵、邻接表、十字链表及邻接多重表的实现细节，对比不同存储方式的时空复杂度，根据场景选择最优存储方案。四大核心算法体系图的遍历掌握DFS（深度优先）与BFS（广度优先）的递归与迭代实现，理解其在连通性检测与图搜索中的应用。最小生成树精通Prim算法（稠密图）与Kruskal算法（稀疏图），解决网络布线、路径规划中的最小成本连接问题。最短路径深入理解Dijkstra单源最短路径算法，掌握Floyd全源最短路径的动态规划思想，优化加权图的路径求解。DAG工程应用利用拓扑排序处理任务依赖关系，通过关键路径算法（CPM）计算项目最短工期，优化工程调度与排期。课程导入与学习目标01抽象概念理解图的存储结构（邻接矩阵、邻接表等）较为抽象，需深刻理解不同结构如何映射顶点与边的关系。这是建立图论思维的基础，也是后续所有算法设计与优化的前提。02算法灵活运用从遍历到最短路径，各类算法逻辑迥异。重点在于理解贪心、动态规划等底层思想，不仅要“会用”，更要能根据实际场景（如稀疏图与稠密图）精准选择最优算法模型。03代码落地实践将抽象逻辑转化为高效代码是关键挑战。需熟练处理复杂数据结构的初始化、边界条件（如自环、负权边）的判定，以及在实际工程中进行时空复杂度的性能调优。🌟学习宗旨：打通“理论理解→算法设计→代码实现”的全链路，建立系统化的图论解题思维。思政元素融入：图的智慧与人生启示网络思维：从拓扑结构看社会协作图论中的“节点”是独立的个体，“边”是联结的纽带。孤立的节点无法传递价值，唯有形成紧密的网络，才能汇聚能量。这映射着人类社会的本质：我们并非孤岛，唯有主动建立联结、彼此信任协作，才能在集体中实现个体价值的最大化，共同编织出坚韧的社会网络。深度优先：择一而专的人生定力如同深度优先搜索（DFS），选定方向便深挖到底。这是一种“咬定青山不放松”的专注，在浮躁的时代里拒绝浅尝辄止，以极致的深耕精神在一个领域扎根，用持续的积累实现从量变到质变的突破，成就专业领域的深度。广度优先：兼容并蓄的视野格局如同广度优先搜索（BFS），层层推进、全面覆盖。这是一种拥抱多元的开放姿态，在成长中广泛涉猎、跨界融合，不断拓展认知的边界。以广博的视野构建立体的知识体系，打破思维定式，从容应对复杂多变的世界挑战。思政元素融入：图的智慧与人生启示精益求精与创新精神：算法演进中的人生哲思工匠精神·极致追求从Dijkstra算法的基础框架到更高效的优化版本，图算法的演进印证了对极致效率的不懈追求。这启示我们在专业领域要拒绝平庸、深耕细作，不满足于“完成”，而要追求“完美”，以匠人之心打磨每一个细节。突破思维·勇于创新图算法的每一次革新，都是对传统路径规划的颠覆与重构。这正是创新精神的体现：敢于质疑既有范式，积极探索未知解法。在面对复杂问题时，我们更应跳出固有思维框架，以创新思维开辟新的道路，不断拓展知识的边界。知行合一：将算法中的优化思维与创新意识融入日常学习与实践，以“日日新”的态度精进自我，让技术能力的提升与思想境界的升华同频共振，真正做到学以致用、用以促学。课程目录01图的定义与基本术语剖析顶点、边、度、连通性等核心概念，构建图论的基础认知框架。02图的存储结构深入掌握邻接矩阵与邻接表的实现原理，理解不同结构的时空效率差异。03图的遍历算法系统学习深度优先搜索(DFS)与广度优先搜索(BFS)，掌握其递归与迭代实现。04连通性与最小生成树探索图的连通分量，并解析Prim算法与Kruskal算法的核心思想与应用。05最短路径算法深入剖析Dijkstra、Bellman-Ford及Floyd算法，解决各类路径规划问题。06有向无环图(DAG)应用掌握拓扑排序算法，并学习关键路径法在工程进度规划中的实际应用。07总结与实战展望回顾图论核心算法体系，结合社交网络推荐、地图导航等场景进行案例分析。🚀开启算法进阶之旅图论是计算机科学的基石，从理论到实践，探索数据结构的无限可能。PART01图的定义与基本术语从顶点与边的构成逻辑出发，深入解析图的核心要素与分类体系。建立对图结构的直观认知，是掌握复杂网络分析与图算法的基石。从树到图——更复杂的关系模型01树：层级分明的“一对多”特殊的图结构，拥有严格的父子层级。除根节点外，每个节点仅有一个父节点，是处理分类、目录等层级数据的基础。02图：自由连接的“多对多”突破层级限制的通用结构，节点间可任意连接。支持多前驱与多后继，能精准表达现实世界中错综复杂的网状关联。社交网络用户是顶点，关注与好友关系是边，构成庞大的无向图，映射真实的人际连接。交通路网城市或站点为顶点，道路或航线为边，用于路径规划与流量分析的经典模型。互联网拓扑路由器与服务器为顶点，光纤链路为边，构建起覆盖全球的复杂通信网络。集成电路电子元件为顶点，金属导线为边，是芯片设计与信号分析的核心数学基础。💡核心洞察：图结构是对现实世界关系最自然、最直接的数学抽象。相较于树的刚性层级，图赋予了数据连接无限的可能性，是处理复杂网络问题的基石。图的定义01形式化定义图(Graph)是一种非线性数据结构，用于描述对象间的多对多关系，其数学模型表示为二元组：G=(V,E)V(Vertex)·顶点集合数据元素的有限非空集合，代表图中的实体对象，如社交网络中的用户。E(Edge)·边集合顶点间关系的有限集合，描述对象间的关联，如用户之间的关注关系。02简单无向图示例以一个包含3个顶点的三角形结构为例，它是典型的无向图模型，体现了节点间的紧密连接：顶点集合V{v₁,v₂,v₃}三个独立的实体节点边集合E{(v₁,v₂),(v₂,v₃),(v₁,v₃)}节点间两两直接相连✦特征：无向图中边没有方向，关系是对称的，如社交网络中的“好友关系”。图的基本类型：无向图01核心定义无向图是图论中最基础的结构，其边不具备方向性。对于任意两个顶点vi和vj，边(vi,vj)与(vj,vi)完全等价，代表顶点间的双向连接，如同生活中的“双向道路”或“好友关系”。02实例解析：图G₁顶点集合V：V={v₁,v₂,v₃,v₄,v₅}

由图中所有独立的节点构成，是图的基本组成单元。边集合E：E={(v₁,v₂),(v₁,v₃),(v₁,v₄),(v₂,v₃),(v₂,v₅),(v₃,v₄)}

由无序顶点对构成，描述了顶点间的具体连接关系。图示为典型的无向图结构，节点间的连线无箭头指向，直观体现了边的无序性与顶点间的对称关系。图的基本类型：有向图01/核心定义与术语有向图的边具有明确的单向性，这种有序的边被称为“弧(Arc)”。有序对<vi,vj>表示从顶点vi指向vj的连接，类似于现实中的“单行道”，体现了不对称的关系。弧尾(Tail)·起点对应有序对中的第一个元素vi，是有向弧的发起端，代表关系的源头。弧头(Head)·终点对应有序对中的第二个元素vj，是有向弧的终止端，代表关系的指向。数学表达示例：G₂=(V,E)顶点集V={v₁,v₂,v₃,v₄}|边集E={<v₁,v₂>,<v₁,v₃>,<v₃,v₄>}注：E中的元素顺序不可调换，<v1,v2>与<v2,v1>代表两条完全不同的弧。图示：典型的有向图结构，节点间的箭头直观地展示了连接的方向性与路径。图的基本术语：完全图01无向完全图每两个顶点之间都有一条无向边相连，边是双向的，不具有方向性。边数最大值：n(n-1)/2n为顶点数量，边数随顶点数呈平方级增长，是连接最紧密的无向图。02有向完全图任意两点间存在方向相反的两条有向弧，边是单向的，体现不对称关系。弧数最大值：n(n-1)弧数是无向完全图边数的两倍，每一对顶点间都建立了双向的连接通道。图的基本术语：稀疏图vs.稠密图稀疏图(SparseGraph)边数e远小于完全图的边数，通常满足e<nlogn。在现实世界中，绝大多数网络结构（如社交网络、计算机网络、路网）都呈现为稀疏图，节点间的连接是不充分的，呈现出“少连接、多孤立”的特征。稠密图(DenseGraph)边数e接近完全图的最大边数（约为n²/2）。此类图中节点间的连接极为紧密，任意两个节点之间大概率存在直接的边相连。常见于高度耦合的系统模型、全连接神经网络层或理论上的完全连通场景。💡关键意义：区分二者是选择存储结构的核心依据——稀疏图适合用“邻接表”节省空间，稠密图则适合用“邻接矩阵”提升查询速度。图的基本术语：网(Network)01/核心定义在图论模型中，若给边或弧赋予具有实际度量意义的数值（如距离、成本、时间），该数值被称为权值(Weight)。这种包含权值信息的图，被正式定义为网(Network)，也常称作“带权图”。权值的典型应用维度地理空间：量化节点间的物理距离（如城市路网里程、坐标间距）。经济成本：代表资源消耗或代价（如运输费用、链路建设成本、网络资费）。02/结构示意图解图中节点（A-F）代表实体对象，连接线上的数字即为权值。例如，A到C的权值为5，可理解为“从A到C的距离为5单位”。权值赋予了图模型量化分析的能力，是解决路径规划、资源分配等问题的基础。图的基本术语：子图(Subgraph)图示：图G及其衍生的子图H、M、Q结构▍数学定义设图G=(V,E)，若存在图G₁=(V₁,E₁)，满足顶点集V₁是V的子集（V₁⊆V），且边集E₁是E的子集（E₁⊆E），则称G₁是G的子图。顶点包含性子图的所有顶点必须是原图顶点集合的一部分，不可包含原图外的新顶点。边的依附性子图中的任意一条边，其两个端点必须属于子图的顶点集，且该边在原图中存在。💡核心价值：子图是图论中分析图结构的基础，如同集合的子集概念，帮助我们将复杂的大图拆解为更简单的单元进行研究。图的基本术语：度(Degree)01无向图的度顶点v的度TD(v)是与该顶点相关联的边的总数目。它直观反映了顶点在图中的连接紧密程度，是衡量图结构特征的基础指标。02有向图的度•入度ID(v)：以v为终点（弧头）的弧的数量。

•出度OD(v)：以v为起点（弧尾）的弧的数量。

•总度公式：TD(v)=ID(v)+OD(v)。03核心性质定理对于任何图，所有顶点的度数之和等于边数的两倍（∑TD(v)=2e）。这是因为每条边都会同时连接两个顶点，为它们各贡献一个度数。💡关键点：度数之和恒为偶数，这是判断一个非负整数序列能否构成图的度数序列的必要条件。图的基本术语：路径(Path)与回路(Cycle)01路径(Path)图中从顶点vp到vq的顶点序列：vp,vi1,vi2,...,vim,vq。路径的长度定义为序列中所包含边的数目，是衡量节点间连通距离的基础指标。02简单路径(SimplePath)路径序列中的所有顶点均不重复出现的路径。它排除了回路与重复访问的情况，是图论中描述“无环连通”的最基础形式，常用于判断节点间的直达性。03回路/环(Cycle)起点与终点为同一个顶点的特殊路径。回路的存在标志着图中包含闭环结构，是区分“树”（无环连通图）与“一般图”的核心特征，也决定了图的拓扑性质。04简单回路(SimpleCycle)除起点和终点外，其余所有顶点均不重复出现的回路。它是图中最基本的不可约闭环，在分析图的连通性、二分图判定及图的遍历算法中具有关键作用。图的基本术语：连通性(无向图)连通(Connected)若从顶点vi到vj存在至少一条路径，则称这两个顶点是连通的。这是图结构中判断两点关系的基础。连通图(ConnectedGraph)若无向图中任意两个顶点之间都连通，则该图为连通图。它是一种全域可达、结构紧密的图模型。连通分量(Component)非连通图的极大连通子图称为连通分量。每个分量内部连通，分量间相互独立，无任何路径可达。图解与核心特征解析左图展示了非连通图G3及其分解出的两个连通分量。

1.极大性：连通分量是无法再扩大的连通子图，是图的“独立单元”。

2.结构意义：连通分量将复杂的非连通图拆解为若干个简单的连通子图，是理解图遍历、图的存储及算法设计的关键基础。图的基本术语：连通性(有向图)01强连通对于有向图中的任意两个顶点vᵢ和vⱼ，若同时存在从vᵢ到vⱼ以及从vⱼ到vᵢ的路径，则称该有向图为强连通图。这是有向图连通性的最强形式。02强连通分量有向图中的极大强连通子图被称为强连通分量。“极大”指该子图本身是强连通的，且无法再向其中加入更多的顶点而保持强连通性。它是分析有向图结构的核心基础。图的基本术语：生成树(SpanningTree)01核心定义连通图的一个极小连通子图，包含图中所有n个顶点，但仅保留足以构成一棵树的n-1条边。它是连通图中保持连通性所需的最少边数的子图，是理解网络拓扑简化的基础。02关键性质生成树本身是无环的连通图；若在生成树中任意添加一条原图中的边，必形成且仅形成一个环；若移除生成树中的任意一条边，图将立即失去连通性。03生成森林(SpanningForest)针对非连通图的扩展概念。由图中每个连通分量各自的生成树共同组成，包含原图的所有顶点，且整体呈现为多棵树的集合，同样满足无环的特性。图解：连通图生成树图示为连通图的生成树形态。所有节点(V0-V6)均被连接且无环路，边数恰好为顶点数减一，直观体现了“极小连通”的核心特征。图解：非连通图生成森林图中存在多个独立的连通分量（如A-F、G-I、J），每个分量都有自己的生成树。这些不相交的树共同构成了整个非连通图的生成森林。图的抽象数据类型(ADT)01数据结构定义VertexSet(顶点集)存储图中所有独立的顶点元素，作为图的基本构成单元，每个顶点拥有唯一的标识ID以区分彼此，是构建图结构的基础。EdgeSet(边集)定义顶点间的关联关系，包含起点、终点及可选的权重值（适用于网图），精准描述顶点间的连接方式与关联强度。IsDirected(有向性标识)布尔型状态标记，决定图的方向特性：有向图边具备单向通行特性，无向图则视为双向互通的连接关系。02核心操作接口Create/AddVertex初始化空图结构，动态将新顶点元素加入集合，完成图的基础构建与扩展。AddEdge(v1,v2,w)建立顶点间连接，支持权重设置，灵活构建无向图、有向图及带权网图。Remove(V/E)安全删除指定顶点并清理关联边，或直接移除两点间的特定边，维护图完整性。IsAdjacent(v1,v2)快速判定两顶点是否直接相连，是图算法中高频使用的基础查询操作。DFS-深度优先遍历从起点递归深入探索，回溯后访问其他分支，适用于连通性检测与路径搜索。BFS-广度优先遍历从起点按层级向外扩展，逐层访问邻点，是求解无权图最短路径的经典方法。GetNeighbors(v)检索并返回顶点v的所有直接邻接点集合，为遍历与分析提供数据支撑。辅助管理接口支持图的清空、拷贝、获取顶点/边总数、判断图是否为空等辅助功能。02图的存储结构从邻接矩阵到邻接表，深入解析图结构在计算机中的底层表示逻辑。掌握高效的存储方式，是理解并优化复杂图算法的基础，也是构建高性能网络应用的关键前提。邻接矩阵(AdjacencyMatrix)01核心原理采用“双数组”存储结构：一维数组用于记录图中所有顶点的基础信息，二维数组（矩阵）则用于精确映射任意两个顶点之间的邻接关系，结构规整且连通性查询效率高。02数值表示规则无权图：两点间有边记为1，无边记为0，直观反映顶点连通性。带权图(网)：有边记录对应权值wij，无边记为∞(无穷大)，体现路径代价。图示：一个包含6个顶点的带权图邻接矩阵示例，矩阵中的数值代表顶点间边的权值，空白位置表示顶点间无边相连（即无穷大）。邻接矩阵：特点与分析核心特点•对称性：无向图的邻接矩阵沿主对角线对称。•度数计算：无向图中，第i行（列）之和即为顶点i的度；有向图中，行和为出度，列和为入度。优劣分析•优势：判断两点是否相邻、获取顶点度数的操作效率极高，时间复杂度为O(1)，实现简单直观。•劣势：稀疏图下空间浪费严重，且添加或删除顶点时，矩阵重构成本高。空间复杂度•复杂度：固定为O(n²)，与图中实际的边数完全无关。•适用场景：仅适用于边数较多的稠密图。对于边数远小于n²的稀疏图，会造成大量内存空间的闲置与浪费。💡核心总结：邻接矩阵是一种“以空间换时间”的存储策略，在稠密图场景下能发挥极致的查询性能，是处理顶点关系固定且紧密连接图结构的首选方案。邻接矩阵：代码实现(伪代码)#defineMaxVerNum100//定义图的最大顶点容量

typedefcharVertexType;//顶点数据类型，如字符'A','B'

typedefintEdgeType;//边类型，0表示无边，1表示有边(或存储权值)typedefstruct{

VertexTypevexs[MaxVerNum];EdgeTypeedges[MaxVerNum][MaxVerNum];intn,e;

}MGraph;//n:顶点数,e:边数,edges:邻接矩阵voidCreateMGraph(MGraph*G){/*构造邻接矩阵表示的图G*/inti,j,k;if(G==NULL)return;

//1.输入顶点数和边数->G->n,G->e;输入顶点信息->G->vexs[]

//2.初始化邻接矩阵为0(无边)->memset(G->edges,0,sizeof(G->edges))

//3.循环输入e条边，对每条边(vi,vj)置G->edges[i][j]=1(有向图)💡核心要点：邻接矩阵通过二维数组存储顶点间的连接关系，结构简单、查找便捷（时间复杂度O(1)），但对于稀疏图会造成空间浪费（空间复杂度O(n²)）。若为无向图，矩阵沿主对角线对称。邻接表(AdjacencyList)核心原理融合顺序存储与链式存储的特性，为图中每个顶点建立独立的单链表。链表节点记录依附于该顶点的边信息，在稀疏图场景下能有效解决邻接矩阵的空间浪费问题。结构组成顶点表：采用顺序存储结构，存储顶点数据及指向其邻接链表的头指针，便于快速查找。边表：采用链式存储，节点包含邻接点在顶点表中的索引、边的权值（网图）以及指向下一个边节点的指针。示意图：无向图的邻接表存储结构。可见顶点表与边表的关联关系，这种结构极大地提高了稀疏图的空间利用率。邻接表：特点与分析空间高效适配空间复杂度为O(n+e)，仅与顶点数(n)和边数(e)相关。对于边数远小于顶点数平方的稀疏图，能极大减少存储空间的浪费，是稀疏图的最优存储选择。顶点度的计算无向图中，顶点的度等于其邻接链表的长度。

有向图中，链表长度为出度；求入度可建立逆邻接表（以该顶点为弧头的边构成的链表），实现快速统计。核心优劣势对比优势：存储高效且边的增删操作便捷，时间成本低。

劣势：判断两顶点是否相邻时，需遍历对应链表，最坏时间复杂度为O(n)，效率不如邻接矩阵。总结：邻接表结合了数组的随机访问特性与链表的动态存储优势，是稀疏图最主流的存储方式。尽管在判断顶点直接连通性上略有损耗，但其在空间效率和动态操作上的巨大优势，使其在图算法（如广度优先搜索BFS、深度优先搜索DFS）中应用极为广泛。邻接表：代码实现(伪代码)#defineMaxVerNum100//最大顶点数定义typedefcharVertexType;//顶点数据类型（字符型）typedefstructEdgeNode{intadjvex;structEdgeNode*next;}EdgeNode;typedefstructVNode{VertexTypedata;EdgeNode*firstedge;}VNode;typedefstruct{VNodeadjlist[MaxVerNum];intn,e;}ALGraph;//n:顶点数,e:边数voidCreateALGraph(ALGraph*G){/*算法核心：输入顶点与边信息，采用"头插法"构建邻接表*///1.初始化顶点表；2.循环读取边并生成边节点；3.插入链表头部}💡核心特点：空间效率高（仅存储实际存在的边），便于查找顶点的所有邻接点，是图论中最常用的存储结构之一。十字链表(OrthogonalList)适用场景：有向图存储专为有向图设计的链式存储结构，完美弥补了邻接表与逆邻接表单独使用时，无法同时高效查询入度与出度的短板。核心原理：双向链表融合将邻接表与逆邻接表结合，每条弧节点同时加入“出边表”（以弧尾为头）和“入边表”（以弧头为头），实现双向快速检索。关键结构：双节点体系顶点节点：存储数据及指向首条出弧/入弧的指针。

弧节点：存储头尾索引，及指向同弧头/同弧尾下一条弧的指针，构建双向关联。核心优势：高效度查询与空间优化仅需一次结构构建，即可同时高效获取任意顶点的出度（出边遍历）与入度（入边遍历），避免了重复存储，在保证查询效率的同时，实现了空间利用率的最大化。邻接多重表适用场景专为无向图设计，解决传统邻接表中同一条边需在两个顶点链表中重复存储的冗余问题，是无向图边操作的最优选择。核心原理每条边仅用一个节点表示，通过指针分别链入两个关联顶点的边表中。结构包含顶点索引、后继边指针及访问标记，实现双边共享。结构优势对边的标记、删除或修改只需操作单个节点，无需同步维护两份数据，极大地提升了图遍历效率，减少了算法实现的复杂度。存储结构对比总结01邻接矩阵空间复杂度：O(n²)

适用场景：稠密图✔优点：结构简单直观，两点连通性判断快

✘缺点：稀疏图空间浪费大，增删顶点困难02邻接表空间复杂度：O(n+e)

适用场景：稀疏图✔优点：节省存储空间，增删边操作便捷

✘缺点：判断两点连通需遍历，速度较慢03十字链表空间复杂度：O(n+e)

适用场景：有向图✔优点：高效解决有向图的出度与入度查询

✘缺点：结构设计复杂，维护成本较高04邻接多重表空间复杂度：O(n+e)

适用场景：无向图✔优点：无需重复存边，简化边的操作

✘缺点：节点结构冗余，实现细节繁琐PART03图的遍历从起点出发，遵循特定规则访问图中所有顶点，是连通性分析、路径搜索与拓扑排序等图算法的核心基础。遍历的概念与挑战核心定义从图中任意一个顶点出发，沿着边访问图中所有顶点，且每个顶点仅被访问一次。这是探索图结构、挖掘网络关系的基础操作。面临的挑战•结构无固定起点，遍历入口选择灵活但复杂

•边的连接易形成回路，极易造成节点重复访问

•若为非连通图，单次遍历无法覆盖全部节点关键解决方案•引入visited[]标记数组，记录状态避免重复

•针对非连通图，循环检查并对未访问节点重新发起遍历

•借助栈（DFS）或队列（BFS）实现有序的遍历过程深度优先搜索(DFS-Depth-FirstSearch)图示：树结构的DFS遍历过程

从根节点出发，优先纵向深入，直至叶子节点再回溯。核心思想：“先走到底，再回头”如同走迷宫，选择一条路径一直探索到尽头，若无路可走则返回到上一个路口，尝试其他分支。本质是树的先根遍历算法的延伸。执行步骤：标记、递归与回溯1.访问起始点并标记；2.选一个未访问邻接点递归搜索；3.若当前节点无未访问邻接点则回溯；4.若图未遍历完，选新起点重复。实现方式：递归/栈(Stack)递归写法最简洁，利用系统栈自动保存状态；非递归写法需显式使用栈结构来模拟递归过程，手动管理待访问节点。DFS：代码实现(邻接表，递归)C语言核心实现//算法8-5:邻接表的深度优先搜索(递归核心)

intvisited[MaxVerNum];//全局访问标记数组，0为未访问

voidDFSAL(ALGraph*G,intv){

EdgeNode*p=G->adjlist[v].firstedge;//取首个邻接点指针

printf("访问顶点:%c\\n",G->adjlist[v].vertex);visited[v]=1;//标记并访问

while(p){//遍历所有邻接点

if(!visited[p->adjvex])DFSAL(G,p->adjvex);//递归深入

p=p->next;

}

}voidDFSTraverseAL(ALGraph*G){//图的DFS遍历入口

inti;//初始化所有顶点状态为未访问

for(i=0;i<G->n;++i)visited[i]=0;

for(i=0;i<G->n;++i)//处理非连通图的所有连通分量

if(!visited[i])DFSAL(G,i);

}核心逻辑：访问当前点→标记已访问→递归访问未被访问的邻接点，确保覆盖图中所有节点。DFS：时间复杂度01邻接表(AdjacencyList)每个顶点仅被访问一次，耗时O(n)；每条边作为出边和入边各被访问一次，总耗时O(e)。两者相加构成了算法的总体时间消耗。总复杂度：O(n+e)02邻接矩阵(AdjacencyMatrix)对于图中的每一个顶点，必须遍历其对应的整行（共n个元素）来检查是否存在邻接点。即使边很少，也需进行完整的行遍历。总复杂度：O(n²)💡结论：邻接表在稀疏图中效率显著优于邻接矩阵；在稠密图中，两者效率差异较小。广度优先搜索(BFS)图示：从根节点开始，按层级顺序

向外扩展，逐层访问所有邻接点核心思想：先广后深，涟漪扩散从起始顶点出发，优先访问其所有直接邻接点（广度），再以这些邻接点为起点，继续向外层扩展，如同水面波纹般层层推进，直到遍历完所有可达节点。执行逻辑：队列驱动的层级遍历1.起始点入队并标记；2.队首节点出队，访问其所有未访问邻接点并标记、入队；3.重复步骤2直至队列为空；4.若图不连通，选择新起点重复。此过程严格保证了节点的层级访问顺序。实现基础：队列(Queue)数据结构利用队列“先进先出(FIFO)”的特性来维护待访问的节点序列，确保先被发现的节点先被处理，从而严格遵循“按层推进”的遍历规则，是实现BFS的关键。BFS：代码实现(邻接矩阵)//算法8-7：基于邻接矩阵的广度优先搜索(BFS)实现voidBFSM(MGraph*G,intk){inti,j;intvisited[MaxVerNum]={0};QueueQ;InitQueue(&Q);printf("访问顶点:%c\n",G->vexs[k]);visited[k]=1;EnQueue(&Q,k);while(!QueueEmpty(&Q)){i=DeQueue(&Q);for(j=0;j<G->n;j++){if(G->edges[i][j]==1&&!visited[j]){printf("访问顶点:%c\n",G->vexs[j]);visited[j]=1;EnQueue(&Q,j);}}}}核心机制解析：利用“队列”实现层级式扩散访问，遵循先进先出(FIFO)原则。从起点开始，每访问一个顶点就将其所有未被访问的邻接点加入队尾，从而保证了访问顺序的“广度优先”特性。该实现的时间复杂度为O(n²)，其中n为图的顶点总数。BFS：时间复杂度与DFS一样，广度优先搜索（BFS）的时间复杂度并非固定，而是由图的具体存储结构决定。不同的存储方式会直接影响遍历的效率。01邻接表(AdjacencyList)•每个顶点仅入队和出队一次，耗时O(n)。

•每条边仅被访问和检查一次，耗时O(e)。

•空间利用率高，适合边数较少的稀疏图。总时间复杂度：O(n+e)02邻接矩阵(AdjacencyMatrix)•对每个顶点，需遍历整行n个元素寻找邻接点，耗时O(n)。

•对n个顶点重复此操作，导致平方级耗时。

•更适合边数接近n²的稠密图。总时间复杂度：O(n²)💡核心洞察：在稀疏图中，邻接表的效率显著优于邻接矩阵；而在稠密图中，两者的性能差异则相对较小。PART04图的连通性与

最小生成树从连通性判定到最小生成树的构建，深入解析图论中的关键模型。

掌握Kruskal与Prim算法，探索如何以最小代价连接复杂网络。连通分量与生成树深度优先生成树(DFS)广度优先生成树(BFS)01连通分量无向图的极大连通子图，是连通性分析的基础。通过DFS或BFS遍历算法，可高效识别并分离出图中所有独立的连通分量。02生成树(SpanningTree)连通图的极小连通子图，包含全部n个顶点和恰好n-1条边，且无环。根据遍历方式不同，衍生出“深度优先生成树”和“广度优先生成树”两种典型结构。03生成森林针对非连通图的扩展概念，是图中各个连通分量的生成树所构成的集合，它保留了原图的全部顶点且不包含任何回路。最小生成树(MST-MinimumSpanningTree)问题背景在一个带权的连通无向图（网）中，寻找一棵生成树，使得树上所有边的权值之和最小。它是图论中经典的组合优化问题，旨在构建总代价最低的连通子图。核心应用场景广泛应用于基础设施规划与网络优化：如城市间光缆铺设、设计最低成本的交通路网、电网布线、以及物流配送的路径成本控制，是工程建设降本增效的关键算法支撑。关键性质(MSTProperty)设U是顶点集V的非空子集，若边(u,v)是所有一端在U、另一端在V-U的边中权值最小的，则此边一定包含在某棵最小生成树中。这是Kruskal和Prim算法的核心理论基石。“贪心策略的经典体现：每一步选择连接已选与未选顶点的最小权值边，最终获得全局最优解。”Prim算法图示展示了从起始顶点出发，逐步连接权值最小的边，将孤立节点纳入生成树的过程。这一过程直观体现了贪心策略在图论中的应用。核心思想：贪心加点法从任意起始顶点开始，将其归入集合U。每一步都选择权值最小的、能连接“已选顶点集合U”与“未选顶点集合V-U”的边，将对应顶点纳入U，直至覆盖所有顶点，最终形成总权值最小的生成树。标准执行步骤01初始化：设起点为u₀，定义集合U={u₀}，空边集TE={}。02寻边：在所有u∈U、v∉U的边中，选择权值最小的边(u,v)。03扩展：将顶点v加入U，将边(u,v)加入边集TE。04终止：重复步骤2-3，直至U包含图中所有顶点，TE即为最小生成树。Prim算法：实现与复杂度辅助数组：lowcost[]记录顶点集合V-U中每个顶点到已选集合U的最小边权值，是算法每一步寻找最小权值边的核心数据依据，决定了下一个加入生成树的顶点。辅助数组：closevertex[]记录与lowcost[]中最小边权相对应的、位于已选集合U中的邻接顶点。它为新加入的顶点提供了“溯源”信息，是构建生成树具体连接关系的关键。时间复杂度：O(n²)——稠密图的最优选择算法执行包含两层嵌套循环，外层循环遍历所有n个顶点，内层循环寻找当前最小边权，因此时间复杂度为O(n²)。由于其效率与图的边数E无关，Prim算法在边数接近n²的稠密图场景下，相比依赖边排序的Kruskal算法具有更显著的性能优势。Prim算法：代码实现(伪代码)//算法8-8:Prim算法(基于邻接矩阵实现)voidPrim(intgm[][MAX],intn,intclose[]){intlowcost[MAX],min,i,j,k=0;//1.初始化：从顶点0出发，构建候选边权值数组for(i=1;i<n;i++){lowcost[i]=gm[0][i];close[i]=0;}//2.迭代n-1次，依次加入n-1个顶点for(i=1;i<n;i++){min=INF;//寻找当前最小权值的边for(j=1;j<n;j++)if(lowcost[j]!=0&&lowcost[j]<min){min=lowcost[j];k=j;}printf("选中边:(%d,%d)权值:%d\n",close[k],k,min);lowcost[k]=0;for(j=1;j<n;j++)if(lowcost[j]!=0&&gm[k][j]<lowcost[j]){lowcost[j]=gm[k][j];close[j]=k;}}}核心机制：采用贪心策略，从起始顶点开始，每次选择连接“已选顶点集合”与“未选顶点集合”的权值最小的边。通过不断更新`lowcost`数组来维护当前的最小边权，逐步扩展直至覆盖所有顶点。Kruskal算法图示：按边权值从小到大依次选择边，判断是否形成环，并构建最小生成树的过程。01/核心思想：贪心“加边法”将所有边按权值从小到大排序，依次选取。若该边连接两个不同的连通分量，则将其加入生成树，直至生成树包含n-1条边（n为顶点总数）。02/关键执行步骤边权排序将图中所有边按权值进行升序排列，为后续的贪心选择提供有序基础。分量初始化将每个顶点初始化为独立的连通分量，利用并查集结构高效管理。选边与合并依次选最小边，若连接不同分量则加入树并合并，直至树边数达标。Kruskal算法：实现与复杂度图示：并查集（Union-Find）结构

通过树形结构高效管理连通性，是算法的核心支撑。核心实现逻辑1.边权排序：将所有边按权值从小到大排序，遵循贪心策略选择最小边。

2.并查集校验：遍历边时，利用并查集快速判断是否形成环，若不形成则合并连通分量，直到所有顶点连通。复杂度与适用场景时间复杂度：O(eloge)，主要消耗在对边的排序操作上。

优势场景：适用于边数较少的稀疏图，在该场景下效率通常优于Prim算法，是构建最小生成树的经典选择。Kruskal算法：代码实现(伪代码)//定义边的结构体，存储顶点对与权值typedefstruct{intv1,v2;intcost;}EdgeType;intFind(intfather[],intv){//查找顶点v的根节点while(father[v]!=v)v=father[v];returnv;}voidKruskal(EdgeTypeedges[],intn,inte){intfather[n],i,j=0;for(i=0;i<n;i++)father[i]=i;//初始化并查集for(i=0;i<e&&j<n-1;i++){//遍历排序后的边intf1=Find(father,edges[i].v1),f2=Find(father,edges[i].v2);if(f1!=f2){father[f2]=f1;j++;//合并集合，无环则选边printf("选中边:(%d,%d),权值:%d\n",edges[i].v1,edges[i].v2,edges[i].cost);}}}核心逻辑：按权值从小到大选边，利用并查集检测是否形成回路，若不形成回路则将该边加入最小生成树，直至选出n-1条边。Primvs.KruskalPrim算法核心：加点策略

从起点开始，每次选择距离当前树最近的顶点加入，逐步向外扩展连通分量。性能：邻接矩阵/O(n²)

复杂度仅与顶点数相关，不受边数影响，在边数较多时表现稳定。场景：稠密图首选

实现逻辑直观简单，无需复杂的数据结构辅助，适合边数接近顶点平方的图。Kruskal算法核心：加边策略

将所有边按权值排序，按顺序选取边，若不形成环则加入，直到连通所有顶点。性能：边集数组/O(eloge)

复杂度主要由边的排序决定，边越少，算法效率越高，适合稀疏图场景。场景：稀疏图首选

实现相对复杂，必须配合“并查集”来高效检测环，是处理稀疏图的最优解。PART05最短路径从最小生成树到核心寻路算法，深入探索图论中连接两点的最优路径策略。这不仅是网络导航的基础，更是解决资源分配与效率优化的关键钥匙。最短路径：问题分类01单源最短路径(SSSP)以图中某一个特定顶点作为起点（源点），计算并求解该点到图中所有其他顶点的最短路径长度及具体路径。典型应用：地图导航与路线规划

日常生活中使用的地图APP，从当前定位（源点）到任意目的地的实时最优路线计算，是其最直观的应用场景。02全源最短路径(APSP)求解图中任意两个不同顶点之间的最短路径，最终构建出一个包含所有顶点对最短距离的全局矩阵。典型应用：物流调度与网络规划

物流配送中心规划、城市间交通路网的全局优化、通信网络中任意节点间的路由成本测算等需要全局视角的场景。核心差异：单源最短路径关注“一点对多点”的辐射能力，全源最短路径则强调“多点对多点”的全局连通性，算法的选择取决于实际业务对路径计算的范围需求。Dijkstra算法(单源最短路径)图示为算法执行的路径推演过程，红色箭头代表已确定的最短路径片段。算法通过不断“贪心”选择最近节点，逐步锁定从源点到各节点的最短距离。01适用场景专为边权非负的带权图设计（含向/无向）。若图中存在负权边，贪心策略会失效，需改用Bellman-Ford或SPFA算法。02核心思想：贪心策略将顶点分为“已确定集”和“待确定集”。每轮从未确定集中选出距离源点最近的顶点，并用它来更新其邻接点的最短路径估值。03关键执行流程①初始化：源点距离设为0，其余为∞；②选点：从未确定集中选最近点u加入确定集；③松弛：通过u更新邻接点v的距离；④迭代：重复②③直到所有顶点都被处理。Dijkstra算法：实现与复杂度01/核心实现机制dist[]最短距离数组

记录各顶点到源点的当前最短路径长度。初始化时源点设为0，其余顶点设为无穷大(∞)，后续逐步松弛更新。visited[]访问标记数组

布尔类型标记，用于确认顶点是否已被纳入“已确定最短路径”的集合S中，防止重复处理和回路。02/算法复杂度分析O(n²)基于邻接矩阵的基础实现中，需进行n次顶点选择，每次选择需遍历n个顶点查找当前最小值，故为平方级复杂度。若采用优先队列（堆）优化，可将时间复杂度降至O((E+V)logV)，适用于稀疏图场景。💡核心思想：采用贪心策略，按路径长度递增的次序，从源点开始逐步向外扩展，确定每个顶点的最短路径。Dijkstra算法：代码实现(伪代码)//初始化距离数组与访问标记voidDijkstra(MGraphG,intv0){intdist[MaxV],visited[MaxV],i,j,u,min;for(i=0;i<G.n;i++){dist[i]=G.edges[v0][i];visited[i]=0;}dist[v0]=0;visited[v0]=1;//逐步确定所有顶点的最短路径for(i=1;i<G.n;i++){min=INF;u=-1;for(j=0;j<G.n;j++)if(!visited[j]&&dist[j]<min){min=dist[j];u=j;}visited[u]=1;for(j=0;j<G.n;j++)if(!visited[j]&&dist[u]+G.edges[u][j]<dist[j])dist[j]=dist[u]+G.edges[u][j];}}核心逻辑解析：外层循环执行n-1次，每次从未访问的顶点中找到距离源点最近的顶点u。随后，通过内层循环对u的所有邻接点进行“松弛”操作，即检查并更新通过u到达邻接点的路径是否更短，从而逐步构建出从源点到所有其他顶点的最短路径树。Floyd-Warshall算法(全源最短路径)适用场景：全源最短路径求解适用于求解加权图中任意两点间的最短路径。可处理负权边，但无法处理包含负权回路的图（会导致路径长度无限减小）。核心思想：动态规划与路径松弛基于动态规划思想，逐步引入顶点作为中间节点来松弛路径。对每一对顶点(i,j)，尝试以顶点k为中转，判断路径i→k→j是否比当前已知的i→j更短，若是则更新最短路径。执行步骤：三层循环松弛操作1.初始化：构建距离矩阵D，D[i][j]为i到j的直接边权（无边为无穷大）。

2.松弛更新：遍历每个中转点k，再遍历所有起点i和终点j，执行松弛：D[i][j]=min(D[i][j],D[i][k]+D[k][j])。

3.结果：最终矩阵D存储了所有顶点对间的最短路径长度。Floyd-Warshall算法：实现与复杂度01/核心实现逻辑基于动态规划思想，利用一个n×n的距离矩阵维护节点间最短路径。通过引入中间节点k，对任意两点(i,j)进行松弛操作，判断并更新`dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])`。💡优势：仅需三层嵌套循环即可完成全源最短路计算，代码极简，易编写与调试。02/时间复杂度分析算法时间复杂度为O(n³)。由于包含三层遍历所有n个顶点的嵌套循环，其效率随顶点数增加呈立方级下降。⚠️局限：适用于稠密图或小规模图计算；当n>200时，计算耗时将显著增加。总结：Floyd-Warshall是解决全源最短路径问题的经典算法，以牺牲时间效率为代价，换取了极致的实现简洁性与代码可读性，是处理小规模图数据的首选方案。Floyd-Warshall算法：代码实现(伪代码)//初始化：距离矩阵=图的邻接矩阵，INF代表无穷大voidFloyd(GraphG){intdist[V][V],i,j,k;for(i=0;i<V;i++)for(j=0;j<V;j++)dist[i][j]=G.edges[i][j];//核心：以k为中转节点，尝试优化所有i到j的路径for(k=0;k<V;k++)for(i=0;i<V;i++)if(dist[i][k]+dist[k][j]<dist[i][j])dist[i][j]=dist[i][k]+dist[k][j];}矩阵初始化直接将距离矩阵初始化为图的邻接矩阵。若两点间无边相连，则距离设为无穷大(INF)。动态松弛机制利用三层循环，将每个节点k作为中间跳板，逐一检查并更新所有节点对(i,j)的最短路径。复杂度分析时间复杂度为O(n³)，空间复杂度为O(n²)。算法结构紧凑，特别适合稠密图的全局最短路径计算。PART06有向无环图（DAG）

及其应用打破循环依赖的桎梏，构建高效的任务拓扑排序与数据流向模型。从编译原理到分布式系统调度，DAG是实现复杂逻辑依赖管理的核心基础。有向无环图(DAG-DirectedAcyclicGraph)核心定义：一种特殊的有向图结构，其本质特征是图中不存在任何有向回路（即无法从任意节点出发，经过若干条有向边后回到该节点）。它是描述具有先后顺序依赖关系的拓扑结构的数学基础。任务调度编排在项目管理、并行计算及工作流引擎中，用于精准描述任务间的前置依赖关系，避免出现循环依赖死锁，实现资源的最优分配与任务的高效并行执行。复杂依赖建模广泛应用于软件包管理系统（如npm、pip）、数据库事务与供应链网络分析，通过拓扑排序自动解析依赖顺序，解决版本冲突与依赖闭环检测问题。计算与编译优化在编译器后端与数学表达式求值中，将表达式转化为DAG以消除公共子表达式的重复计算，极大减少运算冗余，提升代码执行效率与计算资源利用率。AOV网与拓扑排序01/AOV网：活动在顶点的网络•定义：一种有向无环图(DAG)，用顶点表示活动，有向边表示活动间的先后依赖关系（如课程先修）。•约束：图中严禁存在环（回路），否则活动间会形成循环依赖，导致任务无法启动或完成。02/拓扑排序：线性化依赖关系•核心：对AOV网进行顶点排序，使得对于每一条有向边<u,v>，顶点u在序列中总是位于v之前。•意义：将非线性的依赖结构转化为线性的执行序列，解决了具有前置条件的任务调度问题。核心应用与实践价值广泛应用于课程排期、项目管理（关键路径法）、软件编译依赖解析及任务调度系统。它是将复杂网状依赖转化为有序执行计划的基础，确保了流程的逻辑正确性与执行效率。拓扑排序：步骤与实现01初始选择：寻找起点遍历AOV网，筛选并输出一个入度为0的顶点，作为拓扑排序序列的第一个元素，这是整个算法的启动条件。02移除节点：更新依赖从图中删除该顶点及其所有出边，同时将其所有邻接顶点的入度减1，以此消除该节点对后续节点的前置依赖。03循环判断：完成或成环重复操作直至所有顶点输出（排序成功）；若仍有顶点未输出但已无入度为0的顶点，则说明图中存在有向环，无法进行拓扑排序。实现核心：辅助存储结构通常利用队列（Queue）或栈（Stack）来暂存所有当前入度为0的顶点。这种策略能高效地批量处理节点，保证算法的时间复杂度为O(V+E)（V为顶点数，E为边数），是解决依赖调度问题的标准解法。拓扑排序：代码实现(伪代码)//算法核心：基于邻接表的Kahn算法实现

intTopologicalSort(ALGraph*G){intin_degree[MaxV],queue[MaxV],f=0,r=0,cnt=0,i,v;EdgeNode*p;//1.将所有入度为0的顶点入队，作为拓扑排序起点

for(i=0;i<G->vexnum;i++)if(in_degree[i]==0)queue[r++]=i;//2.处理队列，消除出边影响，邻接点入度减1

while(f<r){v=queue[f++];cnt++;//出队并计数

for(p=G->adj[v].first;p;p=p->next)if(--in_degree[p->adjvex]==0)queue[r++]=p->adjvex;}//3.若计数不等于顶点数，说明图中存在有向环

returncnt==G->vexnum?1:(printf("Graphhasacycle!"),0);}关键特性：该算法利用队列筛选入度为0的节点，时间复杂度为O(V+E)。若最终输出的顶点数小于图中总顶点数，则可判定图中存在回路，这是检测有向图是否为有向无环图(DAG)的重要方法。AOE网与关键路径图示：典型的AOE网结构，节点代表事件，带权有向边代表活动及其持续时间，清晰展示了工程中各活动的先后依赖关系。01AOE网(ActivityOnEdgeNetwork)一种以顶点表示事件、有向边表示活动的有向无环图（DAG）。边上的权值代表活动的持续时间，源点代表工程起点，汇点代表工程终点，主要用于估算工程完成的最短时间。02关键路径(CriticalPath)从源点到汇点的最长路径，其路径长度决定了工程的最短工期。路径上的活动为关键活动，若关键活动延期，将直接导致整个工程工期延误，是项目进度控制的核心。💡核心洞察：要缩短整个工程的工期，必须压缩关键路径上至少一个关键活动的持续时间。关键路径：求解步骤01事件最早发生时间(ve)源点为0，后续取前驱最大值：ve[k]=max(ve[j]+weight(<j,k>))02事件最迟发生时间(vl)汇点等于ve，逆推取后继最小值：vl[k]=min(vl[j]-weight(<k,j>))03活动最早开始时间(e)由起点事件决定：e[i]=ve[k]，即事件最早发生时启动活动04活动最迟开始时间(l)由终点事件决定：l[i]=vl[j]-weight(<k,j>)，不影响总工期的最晚启动05锁定关键活动与路径核心判定：满足e[i]==l[i]的活动即为关键活动，构成关键路径核心逻辑：决定工期的关键关键路径是项目网络中耗时最长的路径，它决定了项目的最短工期。通过正逆两次拓扑排序计算时间参数，识别出“无时间余量”的关键活动，从而进行重点监控与资源优化，确保项目按期交付。PART07总结与应用回顾图论核心原理，解析图结构在推荐系统、知识图谱与人工智能领域的关键应用，探索数据连接背后的无限价值与未来可能。本章知识点回顾01核心概念构建图论的认知基石：理解图的数学定义，区分有向/无向、加权/无权等基本类型，掌握顶点、边、度、连通分量等关键术语的内涵。02存储结构对比掌握邻接矩阵（稠密图首选）与邻接表（稀疏图高效）的实现细节，了解十字