。

此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析#xff0c;本人技术…前言

本文基础知识部分来自于b站分享笔记的好人儿的思维导图与王道考研课程感谢大佬的开源精神习题来自老师划的重点以及考研真题。

此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析本人技术有限最终数据清洗结果不够理想相关CSDN文章便没有发出。

考研真题待更新

请注意本文中的部分内容来自网络搜集和个人实践如有任何错误请随时向我们提出批评和指正。

本文仅供学习和交流使用不涉及任何商业目的。

如果因本文内容引发版权或侵权问题请通过私信告知我们我们将立即予以删除。

文章目录

图的应用最小生成树最短路径BFS求无权图的单源最短路径Dijkstra算法两点间最短路径Floyd算法各顶点之间最短路径小结

有向无环图的应用有向无环图描述表达式拓扑排序AOV网逆拓扑排序AOV网小结

关键路径AOE网小结

代码图的存储结构图的遍历最短路径问题导图最小生成树与二分图导图

第六章

E)其中V(G)表示图G中顶点的有限非空集E(G)表示图G中顶点之间的关系边集合

基本术语

连通图强连通图在无有向图中若对任何两个顶点vu都存在从v到u的路径则G是连通图强连通图

子图相关术语

连通分量/极大连通子图该子图是G连通子图将G的任何不在该子图的顶点加入子图不再连通

强连通分量/极大强连通子图该子图是G强连通子图将G的任何不在该子图的顶点加入子图不再强连通

极小连通子图该子图是G的连通子图在该子图中删除任何一条边子图不再连通

无向完全图任意两个点都有一条边有向完全图任意两个点都有两条边稀疏图有很少边或弧的图enlogn稠密图有较多边或弧的图

邻接矩阵法

是指用一个一位数组存储图中顶点的信息用一个二维数组存储图中边的信息邻接关系二维数组即邻接矩阵

无向图

不便于增加和删除结点、存稀疏图浪费大量空间O(n^2)、统计一共有多少条边浪费时间

邻接矩阵A的A^n[i][j]等于由顶点i到j的长度为n的路径数量

邻接表法

图中顶点用一个一维数组存储元素包含指向第一个邻接点的指针存储顶点和头指针的一维数组叫顶点表

若为有向图存储空间为O(|V||E|)若采用邻接表法则找出度易找入度难若采用逆邻接表则找入度易找出度难

有向图邻接表法中顶点vi出度为第i个单链表中结点个数入度为整个单链表中邻接点域值是i-1的结点个数

顶点表结点顶点域边表头指针

若不构建逆邻接表则找入度麻烦、不方便检查任意一对顶点之间是否存在边

领接表

十字链表时针对有向图的存储方式对应于有向图中的每条弧有一个结点对应于每个顶点也有一个结点有向图的邻接表与逆邻接表的结合

顶点结点域结构

首先访问起始顶点v进队列由v出发依次访问v的各个未访问过的邻接顶点w1,w2,…,wi都加入队列起始顶点pop掉

然后依次访问w1,w2,…,wi的所有未访问过的邻接顶点加入队列并pop访问过的顶点

再从这些顶点出发访问所有未被访问过的邻接顶点直到遍历完成利用队列实现

性能分析

BFS需要借助一个队列n个顶点均需要入队一次所以最坏情况下n个顶点在队列O(|V|)

基于邻接矩阵的遍历BFS序列是唯一的基于邻接表的遍历所得到的BFS序列是不唯一的

深度优先搜索

首先访问图中某个起始顶点v由v出发访问与v邻接且未被访问的任一顶点w1再访问与w1邻接且未访问的任一顶点重复

当不能继续向下访问则依次退回到最近被访问的顶点若还有邻接顶点未被访问则从该点继续DFS直到所有顶点均被访问为止用递归实现

性能分析

DFS是一个递归算法需要工作栈辅助最多需要图中所有顶点进栈O(|V|)

基于邻接矩阵的遍历DFS序列是唯一的基于邻接表的遍历所得到的DFS序列是不唯一的

最小生成树

性质解释n个顶点分属已经在生成树上的顶点集U和未在生成树上的顶点集V-U接下来应在连通U和V-U的边中选取权值最小的边

Prim算法

之后选择一个与当前T中顶点集合距离最近的顶点将该点和对应边加入T每次操作后T中顶点数和边数都1

Kruskal算法

开始时为只有n个顶点而无边的非连通图T{V,{}}每个顶点自成一个连通分量

若该边依附的顶点在两个连通分量上则将边加入T否则继续选取下一条边

最短路径

在有向网中A点源点到达B点终点的多条路径中找到一条各边权值之和最小的路径

Dijkstra算法两点间最短路径

维护一个最短路径数组每次选取最短的顶点加入更新加入后的最短路径直到所有顶点都访问

s[]记录是否访问dist[]记录源地到各点最短路径path[]记录前驱结点

初始化集合S初始为{0}源点入集合dist[]初始值dist[i]arcs[0][i]与源点距离

从顶点集合V-S中选出dist[]数组值最小的即选最近的点加入

修改V0出发到集合V-S上任一顶点最短路径长度若dist[j]arcs[j][k]dist[k]则更新dist[k]dist[j]arcs[j][k]

时间复杂度

维护一个各顶点间最短路径二维数组不断试探加入中间结点是否缩短距离三重循环

初始化对任意两个顶点vi和vj若存在边则二维数组上最短路径为权值不存在则最短路径为无穷

逐步尝试在原路径上加入顶点k(k

拓扑序列是对图中所有的顶点如果存在一条从顶点A到顶点B的路径那么在排序中顶点A出现在顶点B的前面

拓扑排序

重复前两个步骤直到当前的AOV网为空或当前网中不存在无前驱的顶点为止后者说明有向图中存在环

时间复杂度

若一个顶点有多个直接后继则拓扑排序通常不唯一若每个顶点有唯一前驱后继则唯一

逆拓扑排序AOV网

项目/信息V1V2V3V4V5V6a1a2a3a4a5a6a7a8求所有事件的最早发生时间ve()032668求所有事件的最迟发生时间vl()042678求所有活动的最早发生时间e()00332266求所有活动的最迟发生时间l()10442567求所有活动的时间余量d()10110301

关键活动d()0的活动就是关键活动a2、a5、a7关键路径V1—V3—V4—V6

比较项目/存储结构V1V2V3V4V5V6最早发生时间ve(k)032668最迟发生时间vl(k)042678

表格二求所有活动的最早发生时间e()、最迟发生时间l()和时间余量d()

项目/信息a1a2a3a4a5a6a7a8最早发生时间e()00332266最迟发生时间l()10442567时间余量d()10110301

关键活动a2、a5、a7

关键路径上的所有活动都是关键活动是决定整个工程的关键因素因此可通过加快关键活动来缩短整个工程的工期

不能任意缩短关键活动因为一旦缩短到一定程度该关键活动可能变成非关键活动

网中的关键路径不唯一只有加快那些包含在所有关键路径上的关键活动才能达到缩短工期的目的

邻接矩阵存储

对于每个点k开一个单链表存储k所有可以走到的点。

h[k]存储这个单链表的头结点int

h[N],

表示点j已经被遍历过q.push(j);}}}最短路径问题导图

朴素Dijkstra适合稠密图无负权值

//初始化b[]标记是否已经访问dist[]表示最短路径path[]表示前驱结点memset(g,0x3f,sizeof

i0;in-1;i){int

j1;jn;j){if((t-1||dist[j]dist[t])!b[j]){tj;}}//更新已访问的点b[t]1;//更新该点其它距离for(int

j1;jn;j)dist[j]min(g[t][j]dist[t],dist[j]);}if(dist[n]0x3f3f3f3f)

return

其中找最短dist[t]需要O(n2)故利用一个堆把该步骤降为O(n)

int

dijkstra(){priority_queuepairint,int,vectorpairint,int,greaterpairint,int

q;dist[1]0;q.push({0,1});while(q.size()){pairint,int

tempq.top();q.pop();if(st[temp.second])

continue;

//若已访问直接跳过若在下方if语句中判断时间差很多st[temp.second]1;//更新操作for(int

ih[temp.second];i!-1;ine[i]){int

je[i];if(dist[j]temp.firstw[i]){dist[j]temp.firstw[i];q.push({dist[j],j});}}}if(dist[n]!0x3f3f3f3f)

return

-1;}bellman-ford负权值若规定k条边最短路径则只能用它O(nm)

for

用back数组备份dist防止串联访问前几条边改变数据后影响后面的访问会破坏k条边的条件

for

bellman_ford(){dist[1]0;for(int

i0;ik;i){memcpy(back,dist,sizeof

dist);

j0;jm;j){if(dist[lines[j].b]back[lines[j].a]lines[j].w){//这里用backdist[lines[j].b]back[lines[j].a]lines[j].w;}}}if(dist[n]0x3f3f3f3f/2)

printf(%d,dist[n]);}SPFAbellman-ford优化一般O(m),最坏O(nm)

在bellman-ford的基础上利用一个队列与广度优先搜索仅将变小的点加入队列中

用一个cnt[]数组维护每个节点的最短路径边数若边数n即有负权边。

需要考虑图不连通故需要初始化时把所有点加入队列且dist都相等即可。

void

spfa(){q.push(1);dist[1]0;st[1]1;while(q.size()){int

//SPFA与Dijkstra不同仅在于标记数组用于标记是否重复进去队列而非是否访问过for(int

je[i];if(dist[j]dist[t]w[i]){dist[j]dist[t]w[i];if(!st[j]){

//改变后进行判断是否需要加入队列st[j]1;q.push(j);}}}}if(dist[n]0x3f3f3f3f)

三重循环用邻接矩阵存储

外层循环每个要加入的点双层循环两个要加入的节点如果可加入其中且路径边短则更新即可。

初始化

朴素Prim算法用于稠密图优化版Prim和Kruskal算法侧重于稀疏图由于堆优化代码长故一般直接用Kruskal算法

Prim

几乎和dijkstra一样区别在标记数组记录的是进入生成树的节点dist数组记录的是各节点到生成树的最短路径

void

j1;jn;j){if(!st[j](t-1||dist[t]dist[j])){tj;}}st[t]1;resdist[t];for(int

j1;jn;j){if(dist[j]g[t][j]){dist[j]g[t][j];}}}}Kruskal

用结构体存边并排序从最短的边找起若两点不在一颗树则连接在一起并查集思想直到所有点都用最短的边连在一起

sort(lines,linesm);

afind(lines[i].a),bfind(lines[i].b);if(a!b){h[b]a;

}并查集中find函数