二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
通俗点讲：就是将图中的节点分到两个集合中，满足：只存在由一个集合中的点指向另一个集合中的点的边。（也就是说两个集合中点不互通）
二分图的一个等价定义是：不含有「含奇数条边的环」的图
因此，如果存在环的话，环的边数只能是偶数，这样才能均分到两个集合中。如果是奇数一定不是二分图。
匹配
边指向一个点成为匹配。已匹配的点不能够再次匹配。
如图，基数为2的匹配
最大匹配
最大基数的匹配。
上面图中最大匹配为：
完美匹配
两个集合中的点，两两匹配。点都是匹配点，但是边不一定是匹配边
判断是否是二分图
使用深度优先搜索，从任意一点开始遍历，对一点进行染色，其相邻如果为染色则染为不同的颜色，如果存在已染色且染色和相邻节点相同，那么表示存在环路（因为环路所以才被染色），且环路边数为奇数（因为相同颜色），那么不是二分图。
匈牙利算法
寻找二分图中的最大匹配
假设：
- 二分图中所有的节点都在一个环上，或者一条通路上。
那么我们只要找到这条最长的路径即可算出最大匹配。
比如最长路径为4，那么最大匹配为2 - 假设二分图是完美匹配
这样我们需要遍历每一个点，然后对已经匹配过的点进行标记。就自然的获得总点数/2的最大匹配
但实际中二分图中并不是单纯的一个环或者是完美匹配。二是两者结合，比如存在几对点的完美匹配，和几个环，或者几个通路。而且通路和环又相互叠加。
解决方法也是上面两种假设的解决方法的叠加:寻找最长通路（路径）和遍历
在二分图中找到的路径总是在两个集合中跳：类似于，左->右->左->右....
因为匹配的概念是左右两个集合中的点一一对应。所以这条路径中的边一定也是匹配边和非匹配边相互交叉。
比图，第二个右，如果左->右是一条匹配边，那么右->左就是非匹配边。
这种路径叫做增广路径。
在匈牙利算法中，我们一边寻找最长增广路径，一边去遍历那些可能的一一匹配的点。
struct Edge
{
int from;
int to;
};
int hungarian_dfs()
{
int counts=0;
//用来记录二分图中的节点数目
int maxNode=10;
//用来记录节点是否已经匹配过了
vector<int> matched(maxNode,-1)
//用来记录在一个递归增长增广路径时，某个节点是否被添加了
//因为找到了一条比原来长的增广路径以后 直接return，所以没有必要回溯
vector<bool> memo(maxNode,false);
//边的集合，记录每个节点指向的边
vector<vector<Edge>> edges;
for(int j = 0 ;j<V.size();j++)
{
if(metched[j] == -1 )
{
memo=vector(maxNode,false);
if(dfs_(j))
{
counts++;
}
}
}
return counts;
}
bool dfs_(int u)
{
//遍历该节点指向的边，去寻找一条更长的增广路径
for(int i=0;i<edges[u].size();i++)
{
//在寻找增广路径时，一个节点没有被添加在该增广路径中是继续
if(memo[edges[u][i].to] == false)
{
//添加到路径中
memo[edges[u][i].to] == true;
//matched(edges[u][i].to) == -1 表示找到了一条更长的路径。
//或者是找到了一条新的路径。可能是全新，也可能是分叉
//dfs_(matched(edges[u][i].to)) 如果该节点已经在一条增广路径中了，
//那么递归的去寻找一条更长的
if(matched(edges[u][i].to) == -1
|| dfs_(matched(edges[u][i].to)))
{
//这两句，纯粹的表示这两个点已经在一条增广路径中了
matched(v)=u;
matched(u)=v;
return true;
}
}
}
return false;
}
在dfs_中，通过遍历点，不断的去增长增广路径，每次增加1（只是说在之前找到的基础上增加了，但是该路径的开头却没有了。），或者是寻找新的分叉和新的路径（通常是一对点，一一匹配）。
每次如果增广路径增加的时候，dfs_的参数，和最终找到的matched(edges[u][i].to) == -1，被增加到路径中，所以每次都增加两个节点。
这样可以确保counts++。
其中保存的metched中存放的就是匹配好的对。
类似流程为：
- 第一轮：A->B
- 第二轮：C->B
递归dfs_(B)给B匹配好的A从新寻找一个新的对象，让C能够匹配B,3而A去匹配新找到的。
C->B->A->D
如果递归没找到，那么C重新从新再去匹配一个，不在匹配B
C->E - 第三轮F->B
同第二轮。
如果F只指向B，那么F将不能匹配到对象
关键字在一个“腾”，让已匹配的再去匹配别的，腾出一个给我。
KM算法
带权重的完备匹配。寻找最大权重的匹配
完备匹配下的最大权匹配
这种算法只有描述，没有原理，算法
