当前位置：首页 > news >正文

《考研408数据结构》第六章（6.4 图的应用）复习笔记

news 2026/7/17 4:07:20

一、第1种应用问题：最小生成树（Prim算法、Kruscal算法）

这里强调一个概念：Prim算法、Kruscal算法都是为了【最小生成树】，而【最小生成树】的意义只在乎【总的权值之和最小】，比如修建铁路网所花费总成本最低。
他【不在乎】A点到B点、C点到D点这种【局部每对点之间路径最短情况】

1、最小生成树概念

【生成树】
所谓【生成树】它得是【树】！！！！树是【没有环的】！！！！！
然后要记住之前树和图的概念学过，【连通分量】=【极大连通子图】
那么一个连通图必然是【有环的】，而它的【连通分量】只能是自己
所以【生成树（没有环！）】不是【连通分量（有环！）】
【最小生成树】
【最小生成树】又跟【生成树】不完全一样
它在【生成树】的基础上要求：【所包含的边权值和要最小】
那么之所以要求【最小生成树】，就是因为我们需要找到一个【路径权值和最小】的【极小连通子图】，可以让"各个节点——>到其他节点的整体路径代价最少"！！！
总结和易错点
1）该图是【各边权值全都（相等/不等）】还是【存在权值（相等/不等）】
【各边权值全都（相等/不等）】：最小生成树唯一&不唯一【存在权值（相等/不等）】：最小生成树可能唯一、也可能不唯一
2）还要注意：【最小生成树】和【n个顶点、n-1条边】的关系：
【n个顶点、n-1条边】的不一定是【最小生成树】
3）由此可以反推：当一个【n个顶点流通图】的【最小生成树不唯一】时
因为最小生成树必然是【n-1条边】不成环
则流通图自然【大于n-1条边】，刚好构成环
4）最后：最小生成树【权值和最小】≠【图的所有最小权值边】都在最小生成树

2、Prim算法

而前面我们学习广度优先、深度优先的时候，都会发现各个点的相邻节点很多，由于没有规则限定【选哪一个相邻节点作为下一个访问的点？】。所以会有各种不同的访问路径顺序！！

所以我们需要用一些规则和算法，使得【每走一步】都按照一定的规则顺序，这样才能求得【最小生成树】！！！Prim算法就是其中一种：
1、基本步骤：
1）首先任选一个起点，然后【起点】加入到表示【已加入】的【集合U】里
然后离这个【起点】最近 (边权值最小) 的点作为下一个访问点，也加入到【集合U】
有的地方把这个【“已加入” 集合】用一个【isJoin数组】表示
还要有一个【最低代价数组】：【lowCast数组】记录【每个点到集合U的最短路径值】
2）然后接着每次都根据【lowCast数组】选择【离集合U最短(权值最小)】的点，加入到【集合U】，然后再更新【lowCast数组】
2、时间复杂度：O( n^2 )
因为第一层要遍历所有节点找路径权值最小的点加入集合、第二层遍历再把lowCast数组更新，合起来就是一个双重循环嘛

3、Kruskal算法

1、基本步骤：
首先把所有【边，以及该边权值】记录下来，然后取出所有点，把它们当成各自独立没边的点
然后开始给它们【找边】，从【边权值从小到大】顺序构建边，直到形成一个【极小连通图】时停下，就生成了【极小生成树】了
这个步骤可以联想到【并查集】
回忆：并查集就是先分成【不同集合】代表【各个独立的树】
那么Kruskal算法不就是先把各个边作为不同集合，然后逐步构建成一整个集合
2、时间复杂度：O(e * log2e)
不知道怎么分析，没有任何学长、王道解释过，所以我也不想研究了
只用记住，【每次查最小权值边是：log2e】，有【e条边】，合起来就是【e * log2e】（为什么我也不知道反正记住就行）

【总结】

逻辑上的区别特点：
Prim算法：【找点】连成图
Kruskal算法：【找边】构建图
所以：二者生成的【最小生成树】可能【相同】也可能【不同】
【Prim算法规则怪谈】：
1、不允许独立【只找新的点】构成【独立的边】
2、不允许在【已经形成好的路径】的点里【重复连边】
3、不允许形成【环】
【Kruskal算法规则怪谈】
1、和Prim不同，只要路径够短，它允许在新的点构建独立的路径边（相当于新的一个分量）
2、也允许在旧路径基础上连新点（只要路径够短）
3、不允许在旧路径重复连边、构成【环】

【例题】

二、第2种应用问题：单源最短路径

1、单源最短路径（BFS/Dijkstra算法）

所谓【单源】：只考虑从【指定一个点】为【起点】，从它出发到各个点之间最短路径情况
所谓【多元】：要考虑【任意一个点】作为【起点】，从它们任一点出发，到各个点最短路径情况
另外这里强调一个概念：BFS、Dijkstra算法都是为了【单源最短路径】，即【局部每对点之间的最短路径】
他【不在乎】最小生成树那种【总的权值之和最小】情况

1）BFS算法：【无权图】单源最短路径

BFS只适合【无权图】
因为各个边路径默认1，【A直接到B】一定比【A间接到B（途经其他点）】短
；
【运行逻辑】
在【visited[n] (检测访问数组)】基础上又加了两个数组：【dist[n]】、【path[n]】
【dist[n]】：记录【起点——>点i (当前路径终点)】的【最短的路径长度】
初始化值都是：∞，表示 “还不存在起点到点i的最短路径”
【path[n]】：记录【该最短路径】中是哪个【直接前驱点——>指向点i】
初始化值都是：-1，表示 “既然都没路径，也就不存在指向点i的前驱”
然后指定一个【起点】之后，该起点的【d[起点]=0】、【path[起点]=-1】
因为 “起点到起点没有路径啊，也没有前驱节点”
接下来按【BFS广度优先搜索】访问各个相邻节点，并更新每个点的【d[i]】、【path[i]】，就可以得到【起点2——>其他任意点最短的路径方案】
其过程就是利用【树的层序遍历】，将【各层路径累加】，求得最短路径长度

2）Dijkstra算法：【带权图】单源最短路径

Dijkstra适合【有权图】和【无权图】
因为各个边路径权值不同，可能出现【A间接到B（途经其他点）】比【A直接到B】短
；
【运行逻辑】
在【visited[n]】、【dist[n]】、【path[n]】基础上又加了1个数组：【final[n]】
【final[n]】：标记是否已经找到【起点到该点】的【最短路径】
初始化值：除了【起点：true】，都是【false】，表示 “还不存在起点到点i的最短路径”
首先：列出表格，用于统计【起点—>某个点】的最短路径
上面说的【final数组】在这就当成一个【集合】，表示记录【已经确认最短路径的点】
默认一开始就把【起点】加入集合第一个元素，因此表格里也不用记录【起点—>起点自己】的最短路径
然后：每个格子记录【起点—>各个点】的【最短路径】
既要记录【起点—>各个点的路径】、还有【该路径长度】
然后对比这几个路径，确定【长度最短的路径】，然后将【该点加入集合】
假设该点是【点i】，上面操作就代表当前已经确认了【起点——>点i：最短距离路径】
（注意，不用怀疑还会检查出有别的路径比刚才记录【起点——>点i】最短路径的还短，每一轮对比的【最短路径】必然是所有【起点——>点i】路径里最短的）
上一轮已经记录了【起点—>点5】的最短长度，没必要再重复记录
上两轮已经记录了【起点—>点5】、【起点—>点4】的最短长度，没必要再重复记录
注意，我们前面说的是每一轮比较的【最小长度】，该路径的已确认是【起点—>点i：最短路径】
但是每一轮没有加入集合、不是最小长度的路径，说明还没有确认【起点—>点i：最短路径】，还可以随时更新
比如下图的【起点—>点2】，前两轮并没有确认【起点—>点2】的最短路径，第三轮检查时检查时发现确实没有更短的【起点—>点2】路径，所以保持【起点—>点5—>点2】这个路径，并且因为它是第三轮长度最短路径，所以确认该路径是【起点—>点2】的最短路径
由此可知上面【表格】和【3个数组】的关系：
只不过是【表格：人类视角好理解】、【数组：给计算机理解的】

但是留意：选项已经给出【明确路径】，让你求最短路径时
别TM按上面这样写，可以直接计算权值，然后比大小就行了啊
【迪杰斯特拉算法规则怪谈】
1、【起点】一旦确定，后续更新路径【不可能更新起点】
2、【已经加入集合】的点早已确认了【起点—>该点：最短路径】，后续【不可能再更新该点的最短路径】！！！！
3、【权值为负数】时不能用迪杰斯特拉算法！！！（我也不知道原理）
所以又可知：一个图的最短路径【一定是一个简单图】，而且绝不考虑【负权值】、【负权回路】的情况（简单图就是绝对没有环路的）

【例题】

2、多源最短路径（Floyd算法）

注意：不需要学得很仔细，因为它只是在大纲内，但考研从未考察过

考研就不可能考【带负权值的图】！！！

【数组】

【例题】

三、第3种应用问题：拓扑排序与逆排序

1、重点概念

所谓【拓扑排序】就是不用再管什么【路径长短】了，我们要想办法让遍历这个图按人类设定的顺序来遍历。
【强调】：这里的顺序并没有要求“顶点编号升序”、“顶点序号降序”，只要满足各个数字只出现一次，那么哪怕是乱序的序列，也可能是符合人类现实需求的顺序。
1）【AOV网】
这就涉及我上面说的，【AOV网】就是按 “人类现实活动的顺序来设定的图”
2）【拓扑排序】必须满足2个条件
3）【拓扑排序】对应的一定是【有向无环图】
首先你要按先后顺序，肯定得是【有向图】
其次【AOV网】、【必备2个条件】都要求了【无环（无回路）】

2、拓扑排序算法过程

首先记住：【每次要访问的点】：【入度为0的点】！！！
所以只要看到拓扑排序，马上锁定【度为0的点】作为【起点】
但是【度为0】的点可能不唯一，所以【拓扑序列】不是唯一的！！
【正式开始拓扑算法】：
1）利用【栈】或【队列】，每次都把【入度为0的点】入栈、入队
2）然后要注意，【访问完一个点（入栈）】后马上【输出（出栈）】
该点出栈时，记得把它【所连的所有边都删掉】！！！
这样图里又会出现【新的入度为0的点】！！！
3）后续全部按这个顺序重复，直到遍历到最后一个【入度为0】的点
注意：最后一个遍历到的点一定是：【出度为0】的点

3、其他【拓扑排序】重点概念！！！

1）【强连通】和【拓扑排序算法】关系
什么叫【强连通图】？就是要每一对点都能存在路径啊，100%一定要有环啊！
【强连通图】除了【顶点只有1】的时候【没有环】；
【强连通图】只要【顶点大于1】都必然【有环】
所以：【强连通图】只要【顶点大于1】，绝对不能应用【拓扑排序】！！！
2）【拓扑序列结果】唯一、不唯一情况
3）【拓扑序列唯一】和【其遍历的图形状唯一性】关系
4）【拓扑】与【邻接矩阵】存储的关系
若有向图的拓扑是【有序的拓扑序列】：则邻接矩阵一定是【三角矩阵】：
【升序】：没有【序号大——>序号小】的路径，矩阵存上三角（i < j）
【降序】：没有【序号小——>序号大】的路径，矩阵存下三角（i > j）
另外注意，【邻接矩阵】有边是【1】，没有边是【无穷】
则如果说【点i】的【某一列全是无穷】：点i【入度为0】
则如果说【点i】的【某一行全是无穷】：点i【出度为0】
5）【拓扑序列唯一性】与【邻接矩阵】的关系

4、【超级宇宙级难度：DFS逆拓扑排序】

基本每一次看图写逆排序，100%会出错！！！超级他妈的绕
100%会错的点：
1、如果当成原生拓扑排序算法，每次入栈“度为0的点”，绝对错！！这他妈是DFS！！
2、出栈时是按【DFS溯回】的逻辑！！！
只是输出【出度为0(没相邻节点了)】，然后要一级一级他妈返回检查还有没有遗漏点
如果某“父节点”还有相邻节点还没访问，就先别他妈出栈！！
记住这张图的规则：
一定一定一定一定要按【DFS深度遍历】的规则【入栈】！！！！
【出栈】一定是【出度为0】的点！！！
【出栈后】溯回！！如果返回的前驱点都是【出度为0】的点才可以出栈！！
给我往死里再练两题：
现在分析重点：【逆拓扑排序】
可以发现【DFS】使用【栈】时候，输出的点是从【栈顶出栈时】才【输出】
而正常的拓扑排序是：从头到尾访问，【只要访问】到一个点就【输出】
所以【DFS用栈：输出的逆拓扑排序！！！！！】，和【正常拓扑】反着来
【混淆点】：
上面2个例子里输出的结果都是 “乱序的啊”，也不是e、d、c、b、a逆序啊
不用管！！！abcde只是我的一个人为乱设的编号！！结合现实中这些乱序反而才是真的一系列事件的顺序
比如图一的正序：aebcd=12345、dcbea=54321，反正你他妈只用知道是逆排序就行了！！！！

【例题】

五、关键路径

1、一些重点概念

1）【AOE网】
它和【拓扑排序的AOV网】一样也是【有向无环图】！！！！
它也可以进行【拓扑排序】
但是和【AOV网】不同
【AOV网】是用【顶点：表示活动】；
【AOE网】是用【边：表示活动】、【顶点：表示触发一项活动发生的事件】！！！
2）【关键路径】以及其相关概念
【关键路径】
要求的是【最长路径】！！！！！！
（与之前学得单源最短路径、最小生成树...算法完全相反）
【关键活动】
就是这条【关键路径（最长路径）】上的活动
【关键时间】
就是整条【关键路径的长度】、【关联路径的权值和】

2、算法过程（解题思路）

1）选择题：人类视觉干瞪法
直接找到【最长路径】就完事了
【关键活动】就是【该路径上的顶点】
【关键路径时长】就是【该路径权值和】
；
；
2）大题思路【传统完整思路】
第一步：求各【顶点】的【最早开始时间】、【最晚开始时间】
【顶点】的【最早开始时间】
【顶点】的【最晚开始时间】
第二步：求各【弧边】的【最早开始时间】、【最晚开始时间】
注意都是指弧的【开始】时间，最早就是【起点】嘛，最晚就是【终点-弧长】
第三步：找出【最早开始=最晚开始】的【弧】
这些弧连起来就是【关键路径】
；
；
3）快速法
简言之：就是每到一个【交汇点】，就判断走哪条是最长路径，保留最长路径，删除短的路径，一次类推
；
【时间余量】
最后一个计算量，简单看一下

【例题】

六、有向无环图表达式

1）【重点】：【各个算法】判断【有无回路】关系
【BFS】只能判断【无向图】的【有无回路】
【DFS】都能判断【有向图】、【无向图】的【有无回路】
【拓扑排序】一定能判断【有无回路】

七、整体这么多算法的【总结】

1）关于【BFS 和 DFS】的【图的应用】
总结对比如图所示：
2）关于【最小生成树】和【最短路径】两个应用领域：
完全不相干，二者是独立的领域，解决不一样的问题！！！
Prim算法、Kruscal算法都是为了【最小生成树】，而【最小生成树】的意义只在乎【总的权值之和最小】，比如修建铁路网所花费总成本最低。
他【不在乎】A点到B点、C点到D点这种【局部每对点之间路径最短情况】
BFS、Dijkstra、Floyd算法都是为了【单源最短路径】，即【局部每对点之间的最短路径】
他【不在乎】最小生成树那种【总的权值之和最小】情况
3）AOE和AOV