深圳地产网站制作公司,网站做的不好会有什么后果,h5模板怎么制作,做传媒网站公司简介前言
本文基础知识部分来自于b站#xff1a;分享笔记的好人儿的思维导图与王道考研课程#xff0c;感谢大佬的开源精神#xff0c;习题来自老师划的重点以及考研真题。此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析#xff0c;本人技术…前言
本文基础知识部分来自于b站分享笔记的好人儿的思维导图与王道考研课程感谢大佬的开源精神习题来自老师划的重点以及考研真题。此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析本人技术有限最终数据清洗结果不够理想相关CSDN文章便没有发出。
考研真题待更新 欢迎订阅专栏408直通车 请注意本文中的部分内容来自网络搜集和个人实践如有任何错误请随时向我们提出批评和指正。本文仅供学习和交流使用不涉及任何商业目的。如果因本文内容引发版权或侵权问题请通过私信告知我们我们将立即予以删除。 文章目录 前言第六章 图图的定义及基本术语概念基本术语小结 图的存储结构邻接矩阵法小结 邻接表法十字链表法有向图邻接多重表无向图 图的遍历广度优先搜索小结 深度优先搜索小结 图的应用最小生成树最短路径BFS求无权图的单源最短路径Dijkstra算法两点间最短路径Floyd算法各顶点之间最短路径小结 有向无环图的应用有向无环图描述表达式拓扑排序AOV网逆拓扑排序AOV网小结 关键路径AOE网小结 代码图的存储结构图的遍历最短路径问题导图最小生成树与二分图导图 第六章 图
图的定义及基本术语 概念
图G由顶点集V和边集E组成记G(V, E)其中V(G)表示图G中顶点的有限非空集E(G)表示图G中顶点之间的关系边集合
基本术语 关系及路径术语 邻接有边/弧相连的两个顶点之间的关系无向图的边(vi, vj)有向图的边vi, vj 关联依附边/弧与顶点之间的关系 顶点的度与该顶点相关联的边的数目记为TD(v) 有向图中顶点的度等于该顶点的入度和出度之和 路径连续的边构成的顶点序列 路径长度路径上边或弧的数目/权值之和 回路环第一个顶点和最后一个顶点相同的路径 简单路径除路径起点和终点可以相同外其余顶点均不相同的路径 简单回路简单环除路径起点和终点相同外其余顶点均不相同的路径 图的术语 无向图每条边都是无方向的 有向图每条边都是有方向的 简单图不存在重复边不存在顶点到自身的边 多重图反之 子图设有两个图G(V, E)和G’(V’, E’)若V’是V的子集且E’是E的子集则称G’是G的子图 网边/弧带权的图 连通图强连通图在无有向图中若对任何两个顶点vu都存在从v到u的路径则G是连通图强连通图 子图相关术语 连通分量/极大连通子图该子图是G连通子图将G的任何不在该子图的顶点加入子图不再连通 强连通分量/极大强连通子图该子图是G强连通子图将G的任何不在该子图的顶点加入子图不再强连通 极小连通子图该子图是G的连通子图在该子图中删除任何一条边子图不再连通 生成树包含无向图G所有顶点的极小连通子图 生成森林对非连通图由各个连通分量的生成树的集合 无向完全图任意两个点都有一条边有向完全图任意两个点都有两条边稀疏图有很少边或弧的图enlogn稠密图有较多边或弧的图
小结 图的存储结构
邻接矩阵法 概念 是指用一个一位数组存储图中顶点的信息用一个二维数组存储图中边的信息邻接关系二维数组即邻接矩阵 无向图 无向图的邻接矩阵是对称的 顶点i的度第i行或第i列中1的个数 有向图 有向图的邻接矩阵可能是不对称的 顶点的出度 第i行元素之和 顶点的入度 第i列元素之和 有向网 缺点 不便于增加和删除结点、存稀疏图浪费大量空间O(n^2)、统计一共有多少条边浪费时间 补充 邻接矩阵A的A^n[i][j]等于由顶点i到j的长度为n的路径数量 小结 邻接表法 概念 图中顶点用一个一维数组存储元素包含指向第一个邻接点的指针存储顶点和头指针的一维数组叫顶点表 每个顶点的所有邻接点构成一个单链表 结构 若为无向图则需要存储两倍的边存储空间为O(|V|2|E|) 若为有向图存储空间为O(|V||E|)若采用邻接表法则找出度易找入度难若采用逆邻接表则找入度易找出度难 有向图邻接表法中顶点vi出度为第i个单链表中结点个数入度为整个单链表中邻接点域值是i-1的结点个数 图的邻接表表示不唯一 实现 顶点表结点顶点域边表头指针 边表结点邻接点域指针域权值若为网 缺点 若不构建逆邻接表则找入度麻烦、不方便检查任意一对顶点之间是否存在边 领接表
十字链表法有向图 概念 十字链表时针对有向图的存储方式对应于有向图中的每条弧有一个结点对应于每个顶点也有一个结点有向图的邻接表与逆邻接表的结合 结构 顶点结点域结构 data域存放顶点数据信息 firstin域 firstout域分别指向以该顶点为弧头或弧尾的第一个弧结点 弧结点域结构 尾域弧尾 头域弧头 hlink域指向弧头相同的下一条弧 tlink域指向弧尾相同的下一条弧 info域弧相关信息 图的十字链表不唯一但一个十字链表表示确定一个图
邻接多重表无向图 概念 对邻接表的边表进行改造得到专门针对存储无向图的邻接多重表 结构 顶点结点域结构 data域存储该顶点的信息 firstedge域指示第一条依附于该顶点的边 弧结点域结构 标志域标记该边是否被搜索过 ivex域 jvex域该边依附的两个顶点在图中位置 ilink域 jlink域分别指向下一条依附于顶点ivex、jvex的边 info域弧相关信息 图的遍历 广度优先搜索 概念 类似于二叉树的层序遍历算法多了标记数组用于确定已访问的结点 算法思想 首先访问起始顶点v进队列由v出发依次访问v的各个未访问过的邻接顶点w1,w2,…,wi都加入队列起始顶点pop掉 然后依次访问w1,w2,…,wi的所有未访问过的邻接顶点加入队列并pop访问过的顶点 再从这些顶点出发访问所有未被访问过的邻接顶点直到遍历完成利用队列实现 性能分析 时间复杂度 邻接矩阵存储方式O(|V|^2) 邻接表存储方式O(|V||E|) 空间复杂度 BFS需要借助一个队列n个顶点均需要入队一次所以最坏情况下n个顶点在队列O(|V|) 基于邻接矩阵的遍历BFS序列是唯一的基于邻接表的遍历所得到的BFS序列是不唯一的
小结 深度优先搜索 概念 类似于树的先序遍历搜索策略是尽可能深地搜索一个图 算法思想 首先访问图中某个起始顶点v由v出发访问与v邻接且未被访问的任一顶点w1再访问与w1邻接且未访问的任一顶点重复 当不能继续向下访问则依次退回到最近被访问的顶点若还有邻接顶点未被访问则从该点继续DFS直到所有顶点均被访问为止用递归实现 性能分析 时间复杂度 邻接矩阵存储方式O(|V|^2) 邻接表存储方式O(|V||E|) 空间复杂度 DFS是一个递归算法需要工作栈辅助最多需要图中所有顶点进栈O(|V|) 基于邻接矩阵的遍历DFS序列是唯一的基于邻接表的遍历所得到的DFS序列是不唯一的 小结 图的应用
最小生成树 概念 生成树所有顶点均由边连接在一起但不存在回路的图 最小生成树权值之和最小的那棵生成树 性质 最小生成树不是唯一的 其对应的边的权值之和总是唯一的且是最小的 最小生成树的边数顶点数-1 算法 算法基于MST性质 性质解释n个顶点分属已经在生成树上的顶点集U和未在生成树上的顶点集V-U接下来应在连通U和V-U的边中选取权值最小的边 Prim算法 概述 每次将代价最小的新顶点加入生成树 实现 开始时从图中任取一个顶点加入树T 之后选择一个与当前T中顶点集合距离最近的顶点将该点和对应边加入T每次操作后T中顶点数和边数都1 以此类推当所有点加入T必然有n-1条边即T就是最小生成树 Kruskal算法 概述 每次选一条权值最小的边边按权值排序使其连通用并查集判断并实现 实现 开始时为只有n个顶点而无边的非连通图T{V,{}}每个顶点自成一个连通分量 然后按照边的权值由小到大不断选取当前未被选取过且权值最小的边 若该边依附的顶点在两个连通分量上则将边加入T否则继续选取下一条边 以此类推直到T中所有顶点都在一个连通分量上 比较
最短路径
在有向网中A点源点到达B点终点的多条路径中找到一条各边权值之和最小的路径
BFS求无权图的单源最短路径 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] 重复步骤2-3n-1次直到所有顶点都包含在S中 时间复杂度 O(|V|^2) 注意 适合稠密图无负权值
Floyd算法各顶点之间最短路径 概述 维护一个各顶点间最短路径二维数组不断试探加入中间结点是否缩短距离三重循环 过程 初始化对任意两个顶点vi和vj若存在边则二维数组上最短路径为权值不存在则最短路径为无穷 逐步尝试在原路径上加入顶点k(k 0,1,…,n-1)为中间结点 若更新后得到路径比原本路径长度短则新路径代替原本路径 时间复杂度 O(|V|^3) 注意 允许图中有带父权值的边但不允许有包含带负权值的边组成回路 适用于带权无向图
小结 有向无环图的应用 有向无环图无环的有向图简称DAG图 用一个有向图表示一个工程的各子工程及其互相制约关系 AOV网顶点表示活动弧表示活动之间的优先制约关系 AOE网弧表示活动以顶点表示活动的开始或结束事件
有向无环图描述表达式 28题为例 操作数在最下层排成一排 按生效顺序加入运算符分层 从底向上检查同层能否合并
拓扑排序AOV网 概述 拓扑序列 拓扑序列是对图中所有的顶点如果存在一条从顶点A到顶点B的路径那么在排序中顶点A出现在顶点B的前面 拓扑排序 对一个有向图构造拓扑序列的过程 过程 从AOV网中选择一个没有前驱的顶点并输出 从网中删除该顶点和所有以它为起点的有向边 重复前两个步骤直到当前的AOV网为空或当前网中不存在无前驱的顶点为止后者说明有向图中存在环 时间复杂度 邻接矩阵存储O(|V|^2) 邻接表存储O(|V||E|) 注意 若一个顶点有多个直接后继则拓扑排序通常不唯一若每个顶点有唯一前驱后继则唯一 若图的邻接矩阵是三角矩阵则存在拓扑排序反之不一定成立
逆拓扑排序AOV网 实现 DFS算法 过程 从AOV网中选择一个没有后继的顶点并输出 从网中删除该顶点和所有以它为终点的有向边 重复前两个步骤直到当前的AOV网为空
小结 关键路径AOE网 概述 关键路径 从源点到汇点的所有路径中具有最大路径长度的路径 关键活动 关键路径上的活动 过程
项目/信息V1V2V3V4V5V6a1a2a3a4a5a6a7a8求所有事件的最早发生时间ve()032668求所有事件的最迟发生时间vl()042678求所有活动的最早发生时间e()00332266求所有活动的最迟发生时间l()10442567求所有活动的时间余量d()10110301
关键活动d()0的活动就是关键活动a2、a5、a7关键路径V1—V3—V4—V6
表格一求所有事件的最早发生时间ve()和最迟发生时间vl()
比较项目/存储结构V1V2V3V4V5V6最早发生时间ve(k)032668最迟发生时间vl(k)042678
表格二求所有活动的最早发生时间e()、最迟发生时间l()和时间余量d()
项目/信息a1a2a3a4a5a6a7a8最早发生时间e()00332266最迟发生时间l()10442567时间余量d()10110301
关键活动a2、a5、a7
关键路径V1—V3—V4—V6 注意 关键路径上的所有活动都是关键活动是决定整个工程的关键因素因此可通过加快关键活动来缩短整个工程的工期 不能任意缩短关键活动因为一旦缩短到一定程度该关键活动可能变成非关键活动 网中的关键路径不唯一只有加快那些包含在所有关键路径上的关键活动才能达到缩短工期的目的 若关键活动耗时增加则整个工程的工期增长 小结 代码
图的存储结构 邻接矩阵存储 g[a][b]存储边a-b 邻接表存储数组模拟 // 对于每个点k开一个单链表存储k所有可以走到的点。h[k]存储这个单链表的头结点int h[N], e[N], ne[N], idx;// 添加一条边a-bvoid add(int a, int b){e[idx] b, ne[idx] h[a], h[a] idx ;}// 初始化idx 0;memset(h, -1, sizeof h); //在头文件cstring中图的遍历 DFS 上面的代码思路可以针对不同题目代码差异大不列举了 BFS queueint q; //STL中的队列容器st[1] true; // 表示1号点已经被遍历过q.push(1);while (q.size()){int t q.front();q.pop();for (int i h[t]; i ! -1; i ne[i]){int j e[i];if (!st[j]){st[j] true; // 表示点j已经被遍历过q.push(j);}}}最短路径问题导图 朴素Dijkstra适合稠密图无负权值 思路 初始化初始化dist邻接矩阵 循环n-1次每次找最短dist[t]用t更新其它点的距离 //初始化b[]标记是否已经访问dist[]表示最短路径path[]表示前驱结点memset(g,0x3f,sizeof g);memset(dist,0x3f,sizeof dist);g[a][b]min(c,g[a][b]); //如果有重边需要选小的//Dijkstrabool dijkstra(){dist[1]0;for(int i0;in-1;i){int t-1;//找最小的distfor(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 0;else return 1;}堆优化的Dijkstra适合稀疏图无负权值 思路 在朴素Dijkstra算法的基础上 初始化初始化dist邻接矩阵 循环n-1次每次找最短dist[t]用t更新其它点的距离 其中找最短dist[t]需要O(n2)故利用一个堆把该步骤降为O(n) 随之用堆更新的时间复杂度上升为O(mlogn)故适合于稀疏图 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 dist[n];else return -1;}bellman-ford负权值若规定k条边最短路径则只能用它O(nm) 思路 思路(很暴力边的存储仅需要用结构体数组即可) for n 次 用back数组备份dist防止串联访问前几条边改变数据后影响后面的访问会破坏k条边的条件 for 所有边 abw dist[b] min(dist[b], back[a]w); //松弛操作 三角不等式dist[b] dist[a]w 补充如果执行n次依然更新了路径说明有n条的最短路径即有负权边 struct line{ //定义结构体int a,b,w;}lines[N];void bellman_ford(){dist[1]0;for(int i0;ik;i){memcpy(back,dist,sizeof dist); //备份防止串联for(int 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(impossible);else 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 tq.front();q.pop();st[t]0; //SPFA与Dijkstra不同仅在于标记数组用于标记是否重复进去队列而非是否访问过for(int ih[t];i!-1;ine[i]){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) printf(impossible);else printf(%d,dist[n]);}Floyd 思路 三重循环用邻接矩阵存储 外层循环每个要加入的点双层循环两个要加入的节点如果可加入其中且路径边短则更新即可。 初始化 for (int i 1; i n; i )for (int j 1; j n; j )if (i j) d[i][j] 0;else d[i][j] INF;// 算法结束后d[a][b]表示a到b的最短距离
void floyd()
{for (int k 1; k n; k ) //每次要加入的点for (int i 1; i n; i ) //加入点ij中for (int j 1; j n; j )d[i][j] min(d[i][j], d[i][k] d[k][j]);
}最小生成树与二分图导图
朴素Prim算法用于稠密图优化版Prim和Kruskal算法侧重于稀疏图由于堆优化代码长故一般直接用Kruskal算法 Prim 思路 几乎和dijkstra一样区别在标记数组记录的是进入生成树的节点dist数组记录的是各节点到生成树的最短路径 void prim(){dist[1]0;for(int i0;in;i){int t-1;for(int 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); //边排序
for(int i0;im;i){ int afind(lines[i].a),bfind(lines[i].b);if(a!b){h[b]a; //若不是一棵树操作reslines[i].c;cnt;}
}并查集中find函数
