【图论】——二分图

文章目录

• 【图论】——二分图
• • 定义
  • 定理
  • 二分图判定
  • • 染色法
  • 二分图最大匹配——匈牙利算法（增广路算法）
  • • 最大匹配
    • 算法思路
    • 代码实现

定义

*若一张 N N N节点无向图可以分为 A , B A,B A,B两个交集为空的非空集合，并且同一集合内部的点之间没有连通边，则称该图为二分图

定理

• 一张二分图中，一定没有不存在点数为奇数的环（否则环内会有点属于两边集合，矛盾）
• 

二分图判定

染色法

• 使用黑白两种颜色，如果一个点当前为白色，则它所有邻边都是黑色
• 因此，当二分图中某一点颜色确定，图中所有点的颜色就都确定了
• 若发生冲突，则说明存在点数为奇数的环
• 可以用一个dfs来实现染色，复杂度为 O ( n + m ) O(n+m) O(n+m)（点数加边数）

int n, m;//点数、边数
int e[N * 2], ne[N * 2], h[N], idx;//邻接表
int color[N];//存储每个点的颜色
void add(int a, int b)//邻接表存储
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
/*
    颜色选择：
    用1，和2代表两种颜色（黑白），切换颜色用3-当前颜色即可
*/
bool dfs(int x, int c)
{
    color[x] = c;//将x染为c
    for (int i = h[x]; i != -1; i = ne[i]) {//遍历x的所有邻边
        int j = e[i];
        if (!color[j]) {//如果没染色就进入下一层染色
            if (!dfs(j, 3 - c))//3-c颜色切换，如果发生冲突返回false
                return false;
        } else if (color[j] == c)//如果染过色但是发生冲突，也是false
            return false;
    }
    return true;//染色顺利，返回true
}
//调用染色法
bool flag = true;//用一个flag标记，初始化为true
for (int i = 0; i < n; i++) {
    if (!color[i]) {
        if (!dfs(i, 1)) {//如果返回了false证明出现冲突
            flag = false;//flag改false，退出
            break;
        }
    }
}

二分图最大匹配——匈牙利算法（增广路算法）

最大匹配

• 任意两条边都没有公共端点，则称为一组匹配，包含边数最多的匹配称为最大匹配
• 若为二分图中的最大匹配，当且仅当该图中不存在该匹配的增广路
• 简而言之，不能有两个点公用一条边，都是 A 1 A_1 A1​对 B 1 B_1 B1​的关系，类似于“一夫一妻”

算法思路

1. 遍历A或B其中一个集合
2. 如果当前点的邻边未被占用，则用这条边将两点相连
3. 如果邻边全部被占用，去寻找他的邻边是否有其他可以未被匹配的点，如果有，则更还邻边的匹配点，让他的邻边空出，让当前点与其相连

代码实现

int e[M], ne[M], h[N], idx;//邻接表存储
bool st[N];//存储枚举的集合点是否匹配
int match[N];//存储匹配对象
int n1, n2, m;//A，B集合元素个数，边数
void add(int a, int b)//邻接表存储
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
bool dfs(int x)
{
    for (int i = h[x]; i != -1; i = ne[i]) {//枚举x的所有邻边
        int j = e[i];
        if (st[j])//如果已经匹配就跳过
            continue;
        st[j] = true;
        if (!match[j] || dfs(match[j])) {
        //当前点为枚举，或被枚举但是可以换点匹配
            match[j] = x;//j与x 匹配
            return true;//匹配成功
        }
    }
    return false;//如果遍历完没有true则该点没法匹配
}
    for (int i = 1; i <= n1; i++) {
        memset(st, false, sizeof st);//每次要把状态清空，每次枚举互不影响，仅有match数组会记录枚举点
        //因为可能枚举到后面之前匹配过的点会换点匹配，如果不清空，为true无法进行
        if (dfs(i))//如果匹配成功，总匹配个数+1
            res++;
    }