2020年9月 – 个人空间

二分图（二部图）

如何判断一个图是否是二分图，二分图就是可以将图分为两个部分，边都是在两个部分之间，而每个部分内部不可以有边相连。

这样如果二部图中存在一个环，那么这个环中的边数必须是偶数，可以画图验证一下三角形、四边形和五边形就知道了。

那么环中的边数是偶数，就可以利用染色算法来进行判别，环是偶数则两种颜色可以交替，否则必定有两个相邻的节点颜色相同。

可以利用BFS算法（结合队列）对二分图进行判别。关键代码如下：

输入：

 public static void main(String[] args) throws Exception{
       
        Scanner sc = new Scanner(System.in);
        //读入数据，并构建邻接表
        int n = sc.nextInt();
        int [] colors = new int[n];
        HashMap <Integer, ArrayList<Integer>> hm = new HashMap<>();
        for (int i = 0; i < n; i++) {
            hm.put(i, new ArrayList<>());
        }
        while (sc.hasNext()) {
            int forward = sc.nextInt();
            int backward = sc.nextInt();
            hm.get(forward).add(backward);
            hm.get(backward).add(forward);
        }
        System.out.println(hm);
        //这里节点的标识与数组的下表一一对应，也是为了简化问题，如果不是一一对应的情况，可能还需要做一次 index -> node 的转换

        for (int i = 0; i < n; i++) {
            int color = colors[i];
            if (color == 0) {
                boolean valid = BFS(hm, colors, i);
                if (!valid) {
                    System.out.println("not valid");
                    System.out.println(Arrays.toString(colors));
                    return;
                }
            }
        }
        System.out.println("valid!");
        System.out.println(Arrays.toString(colors));
    }

    public static boolean BFS(HashMap<Integer, ArrayList<Integer>> hm, int [] colors, int node) {
        LinkedList<Integer> queue = new LinkedList<>();
        colors[node] = 1;
        queue.offerLast(node);
        while(queue.size() != 0) {
            int curNode = queue.pollFirst();
            for (int neighber : hm.get(curNode)) {
                if (colors[neighber] == 0) {
                    colors[neighber] = - colors[curNode];
                    queue.offerLast(neighber);
                } else if (colors[neighber] == colors[curNode]){
                    return false;
                }
            }
        }
        return true;
    }

二分图中一个很重要的问题就是最大匹配问题，最大匹配问题利用匈牙利算法进行求解。

输入:

关键代码如下：

    static int maxn = 100;
    //通过邻接矩阵进行图构建
    static int [][] matrix = new int[maxn][maxn];
    static boolean [] used = new boolean[maxn]; //表示某个轮次中女生是否被匹配过，每轮都初始化
    static int [] nxt = new int[maxn];  //表示整个过程中与女生匹配的男生id ，nxt[1]=2, 表示女1和男2匹配
    static int n = 5;  //表示男生数量为4（数值多1是为了和输入的id从1开始相匹配）
    static int m = 5;  //表示女生数量为4
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        //构建邻接矩阵
        int k = sc.nextInt();
        for (int i = 0; i < k; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            matrix[a][b] = 1;
        }
        
        //开始遍历每个男生，尝试为每个男生匹配女生
        int res = 0;
        for (int i = 1; i <= n; i++) {
            //每轮都要初始化女生是否匹配数组，因为dfs（递归）找增广路的时候需要标识来调整策略
            used = new boolean[m];
            if (DFS(i)) res ++;
        }
        System.out.println(res);
    }
    
    //这个方法是匈牙利算法的核心，函数标识在当前情况下，是否（返回值）能为男x成功匹配到女生。该函数还会修改每次初始化的used数组和nxt全局数组。
    public static boolean DFS(int x) {
        //遍历每个女生看看能不能和男生x匹配上
        for (int i = 1; i <= m; i++) {
            // 如果该女生和男生x存在可匹配的边，并且女生在这一轮没有匹配过
            if (matrix[x][i] == 1 && !used[i]) {
                //标识此轮中该女生被从尝试匹配过，防止递归找增广路的时候重复访问（增广路不是环，因此不能重复访问）
                
                used[i] = true;
                //如果这次循环没有找到，会对其他轮次的循环造成影响吗，因为你修改了used数组
                //不会，因为如果存在一条增广路，经过了上次不成立的增广路，那么上次的也是一条增广路，产生矛盾。

                //如果当前女生没有匹配的男生 || 当前女生有匹配的男生，并且可以让那个匹配的男生去找一个新的女生
                if (nxt[i] == 0 || DFS(nxt[i])) {

                    nxt[i] = x;
                    return true;
                }
            }
        }
        return false;
    }

单单看代码注释还是很难理解，可能过一阵子就忘了，结合代码单个步骤调试会更加形象，后面有空整一个视频讲解吧。

参考文献

月份：2020年9月

二分图（二部图）判别和最大匹配问题（匈牙利算法）