计算基础教程 10

授课内容图论算法学时4教学目标知识目标理解图的基本概念与两种存储结构掌握图的深度优先遍历原理与实现掌握最短路径与最小生成树的核心算法理解拓扑排序的适用场景与执行流程能力目标提升图结构建模与问题抽象能力强化图算法流程分析与代码实现能力培养根据场景选择合适图算法的决策能力重点与难点重点图的邻接矩阵与邻接表存储方式深度优先遍历DFS的递归实现过程Dijkstra与Floyd最短路径算法思路Prim、Kruskal最小生成树构造方法难点图算法的状态更新与边界条件控制最短路径与最小生成树的原理理解教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章是算法学习核心模块，覆盖最常用的图结构问题图论可解决路径规划、网络布线、任务调度等实际问题是程序设计竞赛、等级考试的高频重点章节掌握图算法能显著提升复杂关系建模能力本章由浅入深，为后续复杂图论学习奠定坚实基础第二部分：新课讲解一、图论入门1、基本概念什么是图简单地讲，图是由一组顶点和连接这些顶点的边组成的数据结构。图中数据是一种多对多的关系。有向图与无向图有向图：图的边有方向；无向图：图的边没有方向。权值权值就是边的权重，在计算最短路径、最低通行费用等操作时，需要用到权值。顶点的度顶点的度是指与该顶点相连的边的数量。连通性图的连通性是指图中任意两个顶点之间是否存在路径。稀疏图与稠密图简单地说，稀疏图就是边比较少的图，而稠密图就是边比较多的图。2、图的存储结构邻接矩阵在邻接矩阵中，使用二维数组存储一张图。n个顶点的图需要使用n×n的数组来存储。假设数组定义为：intG[100][100];则G[i][j]的值表示顶点i与顶点j之间边的权值，如下：邻接表邻接表是图的一种链式存储结构，它结合了顺序存储和链式存储的特点，特别适合表示稀疏图。邻接表的核心由二部分构成：顶点数组：用数组存储图中所有顶点。边链表：为每个顶点建立一个单链表，存储与该顶点相关的边。二、图的遍历1、基本概念什么是图的遍历从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种操作称为图的遍历。图遍历操作的特点是：不遗漏、不重复。图的遍历方式图的遍历方式有深度优先遍历和广度优先遍历二种。2、深度优先遍历算法描述图的深度优先遍历（DFS）是一种从起始顶点出发，沿某条路径尽可能深地访问未访问过的邻接顶点，直到路径尽头再回溯的遍历方法。图示程序见课本。三、最短路径1、最短路径概述图的最短路径问题是图论中的经典算法问题，最短路径问题的算法有Dijkstra算法、Bellman-Ford算法、Floyd算法与A*搜索算法等。2、Dijkstra算法算法概述Dijkstra（迪杰斯特拉）算法用来找出从指定的源点开始，到图中全部其余顶点之间的最短距离。此算法不能处理带负边权的最短路径问题。算法思想需要保存一个顶点集S。S中的顶点为已找到了最短路径的顶点。开始时，顶点集S中只有源点这一个顶点。这样，图中的顶点被分为二部分：一部分属于顶点集S；另一部分属于顶点集V-S。接下来，反复执行以下循环，直到顶点集S中包含全部顶点为止：①对于在顶点集V-S中的每个顶点，考察最新加入到顶点集S中的顶点（记为k）是否有边到达自己。如果存在这样的边，则检查从源点经过k点到达自己的路径是否比已知的路径要更短。如果是，则更新从源点到达自己的距离和路径。②完成上一步更新后，从顶点集V-S中寻找一个路径最短的顶点。从源点到这个顶点已不可能有更好的路径了。因此，将其加入到顶点集S内。图示及程序见课本3、Floyed算法概述Floyd算法（弗洛伊德算法）用于计算多源最短路径，即一次性计算出图中任意二个顶点之间的最短距离。Floyd算法可处理负边权的情况，并且代码简单容易理解，但缺点是时间复杂度比较高，达到O(n3)。同时，空间复杂度为O(n2)。算法思想Floyd算法是一个经典的动态规划算法。要寻找从顶点i到顶点j的最短路径，不外乎二种可能，一是直接从顶点i到顶点j；二是从顶点i经过若干个中间顶点到达顶点j。直接从顶点i到顶点j如果顶点i到顶点j之间有边，这二点之间的距离是已知的；否则为无穷大。需要通过中间顶点k假设Dis(i,j)为顶点i到顶点j的最短路径长度，对于每一个中间顶点k，我们检查Dis(i,k)+Dis(k,j)<Dis(i,j)是否成立。如果成立，证明从顶点i到顶点k再到顶点j的路径比从顶点i直接到顶点j的路径短，我们便设置Dis(i,j)=Dis(i,k)+Dis(k,j)。这样一来，当我们遍历完所有中间顶点k，Dis(i,j)中记录的便是顶点i到顶点j的最短路径长度。。图示及程序见课本四、最小生成树1、概念连通图的生成树在一个任意连通图G中，如果取它的全部顶点和一部分边构成一个子图G'，若满足G'中的所有边既能够使全部顶点连通而又不形成任何回路，则称子图G'是原图G的一棵生成树。生成图可以在图的遍历过程中得到，连通图的生成树是不唯一。最小生成树是在无向并且带权图上，使各边权值之和最小的一棵生成树。最小生成树的构造算法最小生成树有二种构造算法，它们均使用了MST性质。Prim（普里姆算法）算法:特点是将顶点归并，与边数无关，适用于稠密图。Kruskal（克鲁斯卡尔算法）算法：特点是将边归并，适用于稀疏图。2、Prim算法算法描述设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})就是最小生成树。例题：最优布线问题【问题描述】学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们间有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。现在由你负责连接这些计算机，任务是使任意两台计算机都连通（不管是直接的或间接的）。【解析】这一个典型的最小生成树问题，使用Prim算法即可解决。程序见课本。3、Kruskal算法算法描述Kruskal（克鲁斯卡尔）算法是一种巧妙利用并查集来求最小生成树的算法。Kruskal算法属于经典贪心算法，先将边按权值排序，然后基于最小生成树性质，不断地选择候选边中权值最小的边，同时保证选中的边不会和已选边构成环，直到选够构成最小生成树所需的n-1条边为止（n为图的顶点数）。构造过程图示例题：最短网络详见课本。五、拓扑排序1、概述概念拓扑排序是针对有向无环图（DAG）的一种线性排序方法。给定一个有向无环图G=(V,E)，其拓扑排序是图中所有顶点的一个线性序列[v1,v2,…,vn]，满足：对于图中的每一条有向边(u,v)∈E，顶点u在序列中都出现在顶点v之前。即：若存在从u到v的有向路径，则u排在v前面。应用场景拓扑排序主要用于解决各种依赖关系问题，它可以检查各种依赖关系是否相互矛盾，并且在没有矛盾的前提下给出一种符合所有依赖关系的排列顺序。算法拓扑排序的实现方法主要有二种：Kahn算法（卡恩算法）和DFS方法（对图进行深度优先搜索）。2、Kahn算法思路基于入度的贪心策略，逐步移除入度为0的节点。此算法需要一个辅助队列。具体步骤：⑴计算图中所有顶点的入度，将入度为0的顶点加入队列。⑵从队首取出一个顶点，将其加入拓扑排序结果序列。⑶遍历该顶点的所有邻接顶点，把它们的入度减1。若某个邻接顶点入度变为0，则加入队列。⑷重复以上步骤，直到队列为空。若结果序列的顶点数等于图的总顶点数，拓扑排序成功；否则说明图中存在环，拓扑排序失败。图解以课本图12-23所示图形为例，使用Kahn算法拓扑排序过程如下：3、应用示例题目：奖金问题见12.5.1节中的引例，要点：在收集了m条意见后，经理想知道：这些意见是否是相互矛盾的？例如：a应该比b高，b应该比c高，c应该比a高。算法分