最小生成树：
简单来说即图中一个使各点连通的N-1个边的子图，当边权和最小时为最小生成树。
经典Prim,Kruskal算法：
- 创建顶点集合V，边集合E
- 初始化V随意取一点u，E为空
- 取与u连接最小的权边与点v，将（u,v）加入E
- 继续重复，取与V中现有点所连接的最小权边，加入到E
- 直到V中包括了所有顶点
每次判断根据点集中现有点，与其他点连接的权值，找最小的权边。
比如V中有U1,U2两点，从整个图中找到与U1或U2所连接的最小权边，并把这个权边的顶点加到V中，更新V变成U1,U2,U3,继续重复。
- 边权排序，各顶点可编不同号
- 选最小，将两顶点标号归并为一类即同号化
- 除去上一个最小，再选最小，判断标号，不同就把所有标号1的点归类到标号2上，相同就不操作继续执行。
- 直到所有顶点为同标号。
通过权值的排序，将权值边从小到大，一步步通过顶点的标号判断归到一起，到最后一定是满足连通无回路条件下的最小权生成树。
最大流问题：
在满足每个边容量限制情况下，流通在图中的最大权值和。
经典的FF，EK，Dinic算法：
- DFS找出一个有效路径
- 生成残余网络，带反向边
- 再在残余图基础上DFS有效路径
- 直到找不到有效路径
- 把每次的最小权值压进每个边中即最大流
深度优先搜索，以最大流最小割为理论依据，残余图无增广路径则最大为判断依据，一直找。 增广路径就是一个有效可通路径的专业叫法而已。
-
与FF算法区别就在于搜索方式，变成了BFS，为什么变成BFS就更快了呢，由于FF搜索是随机的，我们可以把整个图看成无权距离图，或者说每段距离为1的图，BFS即是无权图最短距离的算法。BFS方式下只要搜到终点就是最短的。所以这个方法也可有人称作最短路径搜索法。 -
此算法在EK的基础上，加了一步层次优化，在生成残余网络后层次优化，层次优化是一个分类过程，通过将各点与起点的最短距离或说成相差的最小边数为依据，以BFS方式分成距离起点1条边的，2条边的，3条边的等等，将分成的各类中，相同类中的的边去掉。再去做一次DFS搜索增广路径。 然后生成残余网络再优化，如此循环，每次都全部更新，直到终点不在层次图内结束。
最小费用最大流：
最小费用最大流问题其实十分简单，抽象化后，我们会明显发现，其实就是把之前无权图当作有权图，权值为单位费用价值，用过这个有权的图找最短路径，这就涉及最短路径算法了，一般用SPFA，因为有反向边，要计算负权问题。找到最短路径后，依然通过生成残余网络方式，进行流的迭代增加生成最大流。 每次都在费用权最小条件下向边压进流，最后得到的就是最小费用条件下的最大流。
网友评论