第12章 图论算法

第12章图论算法图论是算法领域的一个重要分支，它研究的是由顶点和边构成的图的性质和应用。本章将介绍图的基本概念、存储结构、遍历方法以及经典的最短路径算法。算法基础目录12.1图论入门12.2图的遍历12.3最短路径12.4最小生成树12.5拓扑排序12.1.1基本概念图的定义：图是由一组顶点（V）和连接这些顶点的边（E）组成的数据结构，graph=(V,E)。有向图与无向图：边有方向的图称为有向图；边没有方向的图称为无向图。权值：边的权重，例如距离、费用等。带权值的图称为有权图。有向图与无向图示意图一、顶点的度在无向图中，顶点的度是指与该顶点相连的边的数量。在有向图中，分为入度（指向该顶点的边数）和出度（从该顶点出发的边数）。二、连通性图中任意两个顶点之间是否存在路径。如果任意两点都有路径，则为连通图；否则为非连通图。12.1.1基本概念连通图与非连通图示意图12.1.2图的存储结构（1）邻接矩阵法邻接矩阵：使用二维数组存储图，G[i][j]表示顶点i和顶点j之间边的权值。若两点间无边，则权值通常记为0或∞。特点：实现简单，判断任意两点间是否存在边的时间复杂度为O(1)；但空间复杂度为O(V²)（V为顶点数），比较耗费空间，因此更适合边数较多的稠密图。无向图及其邻接矩阵12.1.2图的存储结构（2）邻接表法邻接表：为每个顶点建立一个链表，存储与该顶点相连的边。它结合了顺序存储和链式存储的特点，是图的一种重要存储方式。核心特点：1.空间效率高，空间复杂度为O(V+E)；2.特别适合存储稀疏图（边数远小于顶点数）；3.遍历顶点的所有邻接边非常方便快捷。无向图及其邻接表存储示意1.概念从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次。2.特点不遗漏、不重复地访问所有顶点；3.实现要点为了避免重复访问某个顶点，可以设置一个标志数组：boolvisited[n]; 4.遍历方式深度优先遍历和广度优先遍历二种。12.2.1图的遍历1.算法思想从起始顶点出发，沿着一条路径尽可能深地访问未访问的邻接顶点，直到无法继续，然后回溯，尝试其他路径。核心是“先走到底，再回头”。2.实现方案通常采用递归实现，也可通过栈（Stack）模拟递归过程。12.2.2深度优先遍历（DFS）深度优先遍历示意图核心代码实现：boolvisited[n]; //标志数组voiddfs(inti)//深度优先遍历，采用递归形式

{visited[i]=true;cout<<char('1'+i)<<"";//输出顶点i上的文字

for(intj=0;j<n;j++)//扫描邻接矩阵的第i行

if(G[i][j]!=0&&!visited[j])dfs(j);}深度优先遍历程序实现intmain(){//将每个顶点都作为起点来启动一次遍历for(inti=0;i<n;i++)

if(!visited[i])dfs(i);return0;}

策略：贪心策略类型：单源最短路径限制：无负权边Dijkstra算法策略：动态规划类型：单源最短路径特点：可处理负权边，能检测负权环Bellman-Ford算法策略：动态规划类型：多源最短路径特点：时间复杂度高O(V³)，可处理负权边（无负权环）Floyd算法12.3.1最短路径概述Floyd算法问题定义：寻找图中两顶点之间的最短路径，路径权重可以代表距离、时间、费用等。12.3.2Dijkstra算法▍算法思想采用贪心策略，从源点开始，每次选择距离源点最近的未确定顶点，加入已确定集合，并更新其邻接顶点的距离。▍适用场景解决单源最短路径问题。注意：图中不能有负权边，否则算法可能失效。Dijkstra算法执行过程示意（完整图形见课本）核心代码实现逻辑：Dijkstra算法的代码实现需维护三个关键数组：distance[]：记录源点到各顶点的当前最短距离，初始时源点距离为0，其余为无穷大。pre[]：记录路径的前驱节点，用于最终回溯输出最短路径。known[]：标记顶点是否已确定最短路径，避免重复处理。算法核心循环中，每次从未确定的顶点中选择距离源点最近的顶点，标记为已确定；随后遍历其所有邻居节点，通过“松弛操作”更新邻居的最短距离和前驱信息，直至所有顶点处理完毕。Dijkstra算法程序实现12.3.3Floyd算法核心思想：基于动态规划思想，通过三重循环，依次将每个顶点作为中转点，不断更新任意两点间的最短距离。算法思想特点与场景：适用于多源最短路径问题。可处理负权边（无负权环）。代码简洁，但时间复杂度较高（O(V³)）。适用场景核心优势：无需指定源点，直接计算任意两点间的最短路径。实现简单，仅需一个距离矩阵和三重循环即可完成。核心优势核心代码实现：for(intk=1;k<=n;k++) //算法核心，以第k个顶点为中间点进行松驰for(inti=1;i<=n;i++)

for(intj=1;j<=n;j++)

if(e[i][j]>e[i][k]+e[k][j])e[i][j]=e[i][k]+e[k][j];算法解析：外层循环遍历所有可能的中转点k，内层两层循环遍历所有顶点对(i,j)。通过不断松弛操作，判断经过k点是否能让i到j的路径更短。该算法简洁高效，能够处理含负权边的图，但不能处理负权回路。Floyd算法程序实现12.4.1最小生成树1.连通图的生成树在一个任意连通图G中，如果取它的全部顶点和一部分边构成一个子图G'，若满足G'中的所有边既能够使全部顶点连通而又不形成任何回路，则称子图G'是原图G的一棵生成树。2.最小生成树最小生成树是在无向并且带权图上，使各边权值之和最小的一棵生成树。3.最小生成树的构造算法Prim（普里姆算法）算法:特点是将顶点归并，与边数无关，适用于稠密图。Kruskal（克鲁斯卡尔算法）算法：特点是将边归并，适用于稀疏图。12.4.2Prim算法1.算法描述设G=(V,E)是无向连通图，另设U为最小生成树的顶点集，TE为最小生成树的边集。构造步骤:①初始状态：U={u0}，（u0∈V），TE={}。②在所有u∈U，v∈V-U的边中寻找一条权值最小的边(u,v)并入集合TE，同时将v并入集合U中。③重复第②步，直到U=V为止。此时TE中必有n-1条边，T＝(V，{TE})就是最小生成树。12.4.2Prim算法2.算法图示Prim算法下最小生成树生成过程12.4.3Kruskal算法1.算法描述Kruskal（克鲁斯卡尔）算法是一种巧妙利用并查集来求最小生成树的算法。Kruskal算法属于经典贪心算法，先将边按权值排序，然后基于最小生成树性质，不断地选择候选边中权值最小的边，同时保证选中的边不会和已选边构成环，直到选够构成最小生成树所需的n-1条边为止（n为图的顶点数）。12.4.3Kruskal算法2.算法图示Kruskal算法下最小生成树生成过程12.5.1

拓扑排序概述1.什么是拓扑排序？给定一个有向无环图G=(V,E)，其拓扑排序是图中所有顶点的一个线性序列[v1,v2,…,vn]，满足：对于图中的每一条有向边(u,v)∈E，顶点u在序列中都出现在顶点v之前。即：若存在从u到v的有向路径，则u排在v前面。2.应用场景拓扑排序主要用于解决各种依赖关系问题，它可以检查各种依赖关系是否相互矛盾。3.拓扑排序算法主要有二种：Kahn算法（卡恩算法）和DFS方法（对图进行深度优先搜索）。12.5.2

Kahn算法1.算法描述⑴计算图中所有顶点的入度，将入度为0的顶点加入队列。⑵从队首取出一个顶点，将其加入拓扑排序结果序列。⑶遍历该顶点的所有邻接顶点，把它们的入度减1。若某个邻接顶点入度变为0，则加入队列。⑷重复以上步骤，直到队列为空。2.算法图示图论核心知识回顾：课堂小结1.基本概念：掌握图的定义、类型、顶点的度及连通性判定。2.