一、第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算法都是为了【单源最短路径】即【局部每对点之间的最短路径】他【不在乎】最小生成树那种【总的权值之和最小】情况1BFS算法【无权图】单源最短路径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——其他任意点最短的路径方案】​​​​​​​其过程就是利用【树的层序遍历】将【各层路径累加】求得最短路径长度​​​​​​​2Dijkstra算法【带权图】单源最短路径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的点”绝对错这他妈是DFS2、出栈时是按【DFS溯回】的逻辑只是输出【出度为0(没相邻节点了)】然后要一级一级他妈返回检查还有没有遗漏点如果某“父节点”还有相邻节点还没访问就先别他妈出栈记住这张图的规则一定一定一定一定要按【DFS深度遍历】的规则【入栈】【出栈】一定是【出度为0】的点【出栈后】溯回如果返回的前驱点都是【出度为0】的点才可以出栈给我往死里再练两题现在分析重点【逆拓扑排序】可以发现【DFS】使用【栈】时候输出的点是从【栈顶出栈时】才【输出】而正常的拓扑排序是从头到尾访问【只要访问】到一个点就【输出】所以【DFS用栈输出的逆拓扑排序】和【正常拓扑】反着来【混淆点】上面2个例子里输出的结果都是 “乱序的啊”也不是e、d、c、b、a逆序啊不用管abcde只是我的一个人为乱设的编号结合现实中这些乱序反而才是真的一系列事件的顺序比如图一的正序aebcd12345、dcbea54321反正你他妈只用知道是逆排序就行了【例题】五、关键路径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算法都是为了【单源最短路径】即【局部每对点之间的最短路径】他【不在乎】最小生成树那种【总的权值之和最小】情况3AOE和AOV【例题】