数据结构与算法学习笔记15：最大流问题 / 二分图 / 有权无权二分图的匹配 / 匈牙利算法 / 银行家算法 / 稳定婚配
引入小题：最短路径最大流问题（maximum flow problem）简单算法（可能会失败）福特-富尔克森算法（Ford-Fulkerson）时间复杂度Edmonds–Karp算法时间复杂度Dinic Algorithm/又称Dinitz算法层次图概念过程分析时间复杂度二分图 / 二部图（Bipartite Graph）二分图的判定匹配概念无权二部图中的最大匹配问题有权二部图中的最大匹配问题核心方法匈牙利算法（找最小匹配）稳定婚配Gale-Shapley 算法银行家算法Bitmap算法引入小题：最短路径
无权图中，如何找到图中点与点之间的最短路径？
BFS 广度优先遍历
最大流问题（maximum flow problem）
（前提：有边 有权重）
最大流问题是一种组合最优化问题，指的是如何充分利用装置的能力，使得运输的流量最大以取得最好的效果。
简单算法（可能会失败）
1、构建残量图
2、找一条简单路径，找到路径上的瓶颈值（当前路径所允许流过的最大流量），更新残量图路径权值，并将瓶颈值所在边擦除，重复该操作，直到无简单路径。
但实际上，该算法并不一定能够求出最大流，上述图解我们可以看出最大流是2+3=5，但从其他简单路径s→v1→v4→t入手，求解得到的最大流为1+3=4，s→v1→v4→t（不能有更多的水从s流向t，称为阻塞流）。 最大流是阻塞流，但阻塞流不一定是最大流，上述的4就是该题的一种阻塞流。
福特-富尔克森算法（Ford-Fulkerson）
1、构建残量图
2、找一条简单路径，找到路径上的瓶颈值（当前路径所允许流过的最大流量），更新残量图路径权值，并将瓶颈值所在边擦除。
3、添加反向路径
时间复杂度
上例左图为原图，根据原图可容易看出最大流为走s→V1→t和s→V2→t的100+100=200，但在福特-富尔克森算法中，简单路径选择是随意的，如果选择了s→V1→V2→t，则会出现右边的残量图分析过程，后续步骤雷同，共需要200轮才能完成得到最终流量图。若fff表示轮，mmm表示边，则其最坏时间复杂度O(f∗m)O(f * m)O(f∗m)，依赖于流量的时间复杂度，在流量大的时候很致命，这就是福特-富尔克森算法的弊端。
Edmonds–Karp算法
该算法与福特-富尔克森算法（Ford-Fulkerson）相同，只是定义了找到增广路径时的搜索顺序。找到的路径必须是具有可用容量的最短路径（这可以通过BFS广度优先搜索找到）。
时间复杂度
轮数为m*n，其中m为边数，n为顶点个数，其算法时间复杂度为O(m2∗n)O(m^2 * n)O(m2∗n)，相较于前面福特-富尔克森算法最坏时间复杂度O(f∗m)O(f * m)O(f∗m)已有很大提升，但实际上，m边数比n顶点个数肯定要大，因此Dinic算法比Edmonds–Karp算法又好一些。
Dinic Algorithm/又称Dinitz算法
层次图概念
层次图，只有上一层到下一层的边，没有同层的边（同层会增加路径的长度），实际上是帮助求最短路径。
过程分析
1、残量图初始化
2、根据残量图绘制层次图，并根据简单算法寻找阻塞流
3、将阻塞流汇入残量图
4、根据新的残量图更新新的层次图，重复2-4步骤。
时间复杂度
共需要n-1轮，每轮消耗为m * n，即(n-1)(m * n)
因此其时间复杂度为O(m∗n2)O(m * n^2)O(m∗n2)，远小于上个Edmonds–Karp算法的O(m2∗n)O(m^2 * n)O(m2∗n)
二分图 / 二部图（Bipartite Graph）
顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。即G=(u,v,e)G=(u,v,e)G=(u,v,e)，其中u和v内部不可以有边。
二分图的判定
图上随便找一个点开始遍历，相邻的点为两个部分，全部遍历完看看是否有冲突。
步骤：1、任选一个点，颜色标记，入队；2、队首元素拿出，找到相关顶点，如未处理过则标记其他颜色，入队，如处理过则看颜色是否冲突，冲突则over。
如果是非连通图，那就结束后再选一个点进行标记，重复上述步骤，直到再也找不到未被标记的点为止。
实际就是BFS的操作~
匹配概念
匹配指的就是边的集合，但注意其限制，集合内的边顶点是不可以相同的。
如下图中男1女1，男2女3，男3女1（此时女1就相同重复），因此这一组就不是匹配。
最大匹配的概念就是所有匹配中边的数量最大。
无权二部图中的最大匹配问题
MCBM：无权二部图中的最大匹配问题 Maximum-Cardinality Bipartite Matching (MCBM)
实际上该类题用最大流就可解决，前后分别加S和T，所有权值均赋值为1，使用前文算法最终即可得到匹配方案。但注意，最大流的方法只适用于无权图的最大匹配求解，有权图是不可用这个来求最大匹配的。
有权二部图中的最大匹配问题
核心方法
1、将权重符号取反
2、找最小匹配（实际上就是所求的最大匹配）
匈牙利算法（找最小匹配）
要求uv中顶点个数相同，如果不相同可以补全（把边的权值设置为无穷大），时间复杂度为O(n3)O(n^3)O(n3)
步骤分析：
1、根据关系图绘制邻接矩阵；
2、找到每行内的min，然后该行所有元素减去min值；
3、找到每列内的min，然后该列所有元素减去min值；
4、画线；
以最少线覆盖0；（只能画横线or竖线，不能斜！）
判断操作是否结束（若线的条数 = 顶点个数 则结束，否则继续）；
没结束则找到未被线覆盖区域的min，然后未覆盖区域的所有元素减去min值；
线覆盖的交叉点位置加上min值，重复第4步操作……直到线的条数 = 顶点个数 结束。
5、最小匹配；
将所有0对应的边重新构建关系图画出
找到一行中只有一个0的点，以其为基础，将冲突的点进行删除，直到匹配关系成立（无重复顶点）。
6、权值累加计算。
稳定婚配
没有人可以找到比当前更好的配偶
Gale-Shapley 算法
时间复杂度为O(n2)O(n^2)O(n2)
流程分析：
所有人向第一顺位喜欢的人求婚
此时被求婚的人如果未婚，且仅有一人向其求婚，则牵手成功此时被求婚的人如果未婚，且有多人向其求婚，则根据自己的排名进行顺位，选追求者中最喜欢的结婚此时被求婚的人如果已婚，看追求者和现配偶间更喜欢谁，相应完成拒绝追求者或与配偶离婚的操作
银行家算法
一种最有代表性的避免死锁的算法
应用前提条件
1、固定数量的进程共享固定数量的资源；
2、每个进程要预先指定完成工作所需的最大资源数量；
3、每个进程不能申请比系统可用资源总数还多的资源；
4、每个进程等待资源的时间是有限的；
5、如果系统满足了进程对资源的最大需求，那么进程应该在有限时间内使用资源然后归还给系统。
算法分析
1、需要存储可分配的资源数量AAA
2、需要知道当前进程已得到的资源BBB
3、需要知道当前进程所需的最大资源数量CCC
4、需要知道进程还需要的资源DDD
5、需要知道每一次的需求EEE
当某一个进程提出资源申请时（E）：
1、E≤DE≤DE≤D，否则直接报错
2、E≤AE≤AE≤A，否则需要等待
3、满足2的条件（系统给了），更新系统各个部分的资源：A=A−E；B=B+E；D=D−EA=A-E；B=B+E；D=D-EA=A−E；B=B+E；D=D−E
检测系统安全性：① 看标记（是否被检查过）；② 如果没被检查，则检查，看是否满足D＜FD＜FD＜F，满足的话则进行分配，更新FFF，然后进行标记（已检查），如果不满足，那么需要把状态恢复（把前面步骤中：A=A−EA=A-EA=A−E；B=B+EB=B+EB=B+E；D=D−ED=D-ED=D−E全部恢复成更新前的样子，然后进行下一次重新分配）。（FFF为目前可用资源数量，其实和上述的AAA差不多，但AAA和FFF也有一些区别，FFF是检查的时候用的，各个进程都需要进行安全性检查，给一号进程检查完检查二号的时候，FFF就不是一号的FFF了，是被更新过减去一号分配后的…以此类推。）
Bitmap算法
Bitmap算法是用bit数组来记录0-1两种状态，然后再将具体数据映射到这个比特数组的具体位置，这个比特位设置成0表示数据不存在，设置成1表示数据存在。Bitmap算法和布隆过滤器主要解决大数据去重的问题。用于对大量整型数据做去重和查询。
学习链接：数据结构与算法必知— Bitmap位图与布隆过滤器 - 简书 ()
数据结构与算法学习笔记15：最大流问题 / 二分图 / 有权无权二分图的匹配 / 匈牙利算法 / 银行家算法 / 稳定婚配
