2023年7月30日发(作者：)

图论经典算法⼀.问题类1.路径问题柯尼斯堡七桥问题：在所有桥都只能⾛⼀遍的前提下，如何才能把这个地⽅所有的桥都⾛遍？哈密顿回路问题：哈密顿图是⼀个⽆向图,由指定的起点前往指定的终点，途中经过所有其他节点且只经过⼀次。最⼩⽣成树问题：有⼀个有权⽆向图,找到路径把所有顶点连起来,并保证边上权重和最⼩中国邮路问题：此问题为在⼀个连通的⽆向图中找到⼀最短的封闭路径，且此路径需通过所有边⾄少⼀次。最短路问题：最短路径问题是图论研究中的⼀个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。斯坦纳树：最⼩⽣成树是在给定的点集和边中寻求最短⽹络使所有点连通。⽽最⼩斯坦纳树允许在给定点外增加额外的点，使⽣成的最短⽹络开销最⼩。旅⾏商问题（NP困难）：假设有⼀个旅⾏商⼈要拜访n个城市，他必须选择所要⾛的路径，路径的限制是每个城市只能拜访⼀次，⽽且最后要回到原来出发的城市。路径的选择⽬标是要求得的路径路程为所有路径之中的最⼩值。2.⽹络流与匹配2.1最⼤流问题：最⼩费⽤最⼤流问题: 在⼀个⽹络中每段路径都有“容量”和“费⽤”两个限制的条件下，此类问题的研究试图寻找出：流量从A到B，如何选择路径、分配经过路径的流量，可以达到所⽤的费⽤最⼩的要求。在实际中：n辆卡车要运送物品，从A地到B地。由于每条路段都有不同的路费要缴纳，每条路能容纳的车的数量有限制，如何分配卡车的出发路径可以达到费⽤最低，物品⼜能全部送到。3.染⾊3.1四⾊问题：每个⽆外飞地的地图都可以⽤不多于四种颜⾊来染⾊，⽽且不会有两个邻接的区域颜⾊相同

⼆.算法类1.戴克斯特拉算法(D.A)2.最短路径快速算法(SPFA)3.弗洛伊德算法(Floyd-Warshall)解决任意两点间的最短路径的⼀种算法，可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题，同时也被⽤于计算有向图的传递闭包.4. 克鲁斯卡尔算法(K.A)把所有边选出来,并按照权重进⾏排序,从权重最⼩边开始选择,每次选择⼀条边,每次选择的边不能与原来的边构成环,知道选择的边包含所有的节点.5. 普⾥姆算法(P.A)加权连通图⾥搜索最⼩⽣成树6. 拓扑排序算法(TSA)原理:重复以下两个步骤,即可以得到拓扑序列.1.在有向图中任意选择⼀个⽆前驱的节点,并且作为当前的拓扑序列输出2.删除与 前⾯选择的⽆前驱节点 的所有关联的边下⾯是得到其中⼀个拓扑序列的过程:第⼀步:a是⽆前驱的节点,选择第⼆步:a去掉后,b,c为⽆前驱节点,任选⼀个,假设选择c第三步:a,c去掉,只有b为⽆前驱节点,选择第四步:a,c,b去掉后,d,e为⽆前驱节点,任选⼀个,假设选择d第五步:a,c,b,d去掉后,e,f为⽆前驱节点,任选⼀个,假设选择f第六步:a,c,b,d,f去掉后,只有e为⽆前驱节点,选择第六步:a,c,b,d,f,e去掉后,只有g为⽆前驱节点,选择第七步:所有节点遍历完成,得到拓扑序列最终得到的拓扑序列为a->c->b->d->f->e->g7. 关键路径算法(CPA)描述:关键路径： 在AOE⽹中，从始点到终点具有最⼤路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径,⼀个AOE⽹中不⼀定只有⼀条关键路径，可能会有多条。关键活动： 关键路径上的活动（边）。由于AOE⽹中的某些活动能够同时进⾏，故完成整个⼯程所必须花费的时间应该为始点到终点的最⼤路径长度。关键路径长度是整个⼯程所需的最短⼯期。8. ⼴度优先搜索算法(BFS)9.深度优先搜索算法(DFS)