每日算法 — 使用java实现二分图判定：BFS染色与奇环检测

问题描述

二分图（Bipartite Graph）是一种特殊的无向图，其顶点可以被分成两个不相交的集合，使得图中的每一条边都连接两个不同集合中的顶点。换句话说，图中不存在奇数长度的环。

二分图判定问题：给定一个无向图，判断它是否是二分图。如果是，输出一种合法的染色方案。

算法思路

核心定理

一个无向图是二分图，当且仅当它不包含奇数长度的环。

BFS染色法

1. 任选一个未染色的顶点，将其染成颜色0
2. 使用BFS遍历其邻居，将邻居染成相反的颜色1
3. 如果发现某个邻居已经被染成相同的颜色，则存在奇环，不是二分图
4. 重复上述过程，直到所有连通分量都被处理

DFS染色法

与BFS类似，使用深度优先搜索进行染色，原理相同但实现略有差异。

Java实现

BFS染色判定

import java.util.*;

public class BipartiteCheck {
    /**
     * 使用BFS染色判定二分图
     * colors: -1表示未染色, 0和1表示两种颜色
     *
     * @param graph 邻接表表示的无向图
     * @return 如果是二分图返回true，否则false
     */
    public static boolean isBipartiteBFS(List<Integer>[] graph) {
        int n = graph.length;
        int[] colors = new int[n];
        Arrays.fill(colors, -1); // -1表示未染色

        for (int start = 0; start < n; start++) {
            if (colors[start] != -1) {
                continue; // 已染色，跳过
            }

            Queue<Integer> queue = new LinkedList<>();
            queue.offer(start);
            colors[start] = 0; // 起始点染成颜色0

            while (!queue.isEmpty()) {
                int u = queue.poll();
                for (int v : graph[u]) {
                    if (colors[v] == -1) {
                        // 邻居未染色，染成相反颜色
                        colors[v] = colors[u] ^ 1;
                        queue.offer(v);
                    } else if (colors[v] == colors[u]) {
                        // 邻居已染成相同颜色，存在奇环
                        return false;
                    }
                }
            }
        }

        return true;
    }

    /**
     * 返回染色方案，如果不是二分图返回null
     */
    public static int[] getColoring(List<Integer>[] graph) {
        int n = graph.length;
        int[] colors = new int[n];
        Arrays.fill(colors, -1);

        for (int start = 0; start < n; start++) {
            if (colors[start] != -1) continue;

            Queue<Integer> queue = new LinkedList<>();
            queue.offer(start);
            colors[start] = 0;

            while (!queue.isEmpty()) {
                int u = queue.poll();
                for (int v : graph[u]) {
                    if (colors[v] == -1) {
                        colors[v] = colors[u] ^ 1;
                        queue.offer(v);
                    } else if (colors[v] == colors[u]) {
                        return null; // 不是二分图
                    }
                }
            }
        }

        return colors;
    }

    /**
     * 使用DFS染色判定二分图
     */
    public static boolean isBipartiteDFS(List<Integer>[] graph) {
        int n = graph.length;
        int[] colors = new int[n];
        Arrays.fill(colors, -1);

        for (int i = 0; i < n; i++) {
            if (colors[i] == -1) {
                if (!dfs(graph, i, 0, colors)) {
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean dfs(List<Integer>[] graph, int u, int color, int[] colors) {
        colors[u] = color;
        for (int v : graph[u]) {
            if (colors[v] == -1) {
                if (!dfs(graph, v, color ^ 1, colors)) {
                    return false;
                }
            } else if (colors[v] == color) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        // 测试1：二分图（偶环）
        List<Integer>[] graph1 = new ArrayList[4];
        for (int i = 0; i < 4; i++) graph1[i] = new ArrayList<>();
        graph1[0].add(1); graph1[1].add(0);
        graph1[1].add(2); graph1[2].add(1);
        graph1[2].add(3); graph1[3].add(2);
        graph1[3].add(0); graph1[0].add(3);
        System.out.println("图1（偶环C4）是二分图：" + isBipartiteBFS(graph1));
        int[] coloring1 = getColoring(graph1);
        System.out.println("染色方案：" + Arrays.toString(coloring1));

        // 测试2：非二分图（奇环）
        List<Integer>[] graph2 = new ArrayList[3];
        for (int i = 0; i < 3; i++) graph2[i] = new ArrayList<>();
        graph2[0].add(1); graph2[1].add(0);
        graph2[1].add(2); graph2[2].add(1);
        graph2[2].add(0); graph2[0].add(2);
        System.out.println("\n图2（奇环C3）是二分图：" + isBipartiteBFS(graph2));

        // 测试3：非连通二分图
        List<Integer>[] graph3 = new ArrayList[6];
        for (int i = 0; i < 6; i++) graph3[i] = new ArrayList<>();
        graph3[0].add(1); graph3[1].add(0);
        graph3[2].add(3); graph3[3].add(2);
        graph3[4].add(5); graph3[5].add(4);
        System.out.println("\n图3（三个不连通的边）是二分图：" + isBipartiteBFS(graph3));
        int[] coloring3 = getColoring(graph3);
        System.out.println("染色方案：" + Arrays.toString(coloring3));
    }
}

扩展：二分图最大匹配（匈牙利算法）

public class HungarianAlgorithm {
    /**
     * 匈牙利算法求解二分图最大匹配
     * @param graph 左侧顶点到右侧顶点的邻接表
     * @param nLeft 左侧顶点数
     * @param nRight 右侧顶点数
     * @return 最大匹配数
     */
    public static int maxMatching(List<Integer>[] graph, int nLeft, int nRight) {
        int[] matchR = new int[nRight]; // matchR[j]表示右侧顶点j匹配的左侧顶点
        Arrays.fill(matchR, -1);
        int result = 0;

        for (int u = 0; u < nLeft; u++) {
            boolean[] seen = new boolean[nRight];
            if (bpm(graph, u, seen, matchR)) {
                result++;
            }
        }

        return result;
    }

    private static boolean bpm(List<Integer>[] graph, int u, boolean[] seen, int[] matchR) {
        for (int v : graph[u]) {
            if (seen[v]) continue;
            seen[v] = true;

            if (matchR[v] < 0 || bpm(graph, matchR[v], seen, matchR)) {
                matchR[v] = u;
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        // 示例：5个工人和5个任务
        int nLeft = 5, nRight = 5;
        List<Integer>[] graph = new ArrayList[nLeft];
        for (int i = 0; i < nLeft; i++) graph[i] = new ArrayList<>();

        graph[0].addAll(Arrays.asList(0, 1));
        graph[1].addAll(Arrays.asList(0, 2));
        graph[2].addAll(Arrays.asList(1, 2, 3));
        graph[3].addAll(Arrays.asList(2, 4));
        graph[4].addAll(Arrays.asList(3, 4));

        System.out.println("最大匹配数：" + maxMatching(graph, nLeft, nRight));
    }
}

扩展：判断一般图的奇环

public class OddCycleDetection {
    /**
     * 使用BFS染色检测图中是否存在奇环
     * 返回值：如果存在奇环返回true
     */
    public static boolean hasOddCycle(List<Integer>[] graph) {
        return !BipartiteCheck.isBipartiteBFS(graph);
    }

    /**
     * 找出一个奇环上的顶点（如果存在）
     */
    public static List<Integer> findOddCycle(List<Integer>[] graph) {
        int n = graph.length;
        int[] colors = new int[n];
        int[] parent = new int[n];
        Arrays.fill(colors, -1);
        Arrays.fill(parent, -1);

        for (int start = 0; start < n; start++) {
            if (colors[start] != -1) continue;

            Queue<Integer> queue = new LinkedList<>();
            queue.offer(start);
            colors[start] = 0;

            while (!queue.isEmpty()) {
                int u = queue.poll();
                for (int v : graph[u]) {
                    if (colors[v] == -1) {
                        colors[v] = colors[u] ^ 1;
                        parent[v] = u;
                        queue.offer(v);
                    } else if (colors[v] == colors[u]) {
                        // 找到奇环，回溯路径
                        List<Integer> cycle = new ArrayList<>();
                        int x = u, y = v;
                        // 找到x和y的最近公共祖先
                        Set<Integer> pathX = new HashSet<>();
                        while (x != -1) {
                            pathX.add(x);
                            x = parent[x];
                        }
                        while (!pathX.contains(y)) {
                            cycle.add(y);
                            y = parent[y];
                        }
                        cycle.add(y); // LCA
                        x = u;
                        List<Integer> pathFromU = new ArrayList<>();
                        while (x != y) {
                            pathFromU.add(x);
                            x = parent[x];
                        }
                        Collections.reverse(pathFromU);
                        cycle.addAll(pathFromU);
                        return cycle;
                    }
                }
            }
        }
        return null;
    }
}

复杂度分析

实际应用

1. 任务分配：将任务和工人建模为二分图，最大匹配即最优分配
2. 棋盘覆盖：棋盘黑白染色本身就是二分图，相关覆盖问题可转化
3. 冲突消解：将冲突双方分为两组，判断是否存在合法分组
4. 推荐系统：用户-物品二分图是协同过滤的基础模型

总结

二分图判定是图论入门的重要问题。BFS染色法利用二分图的本质特征（无奇环），通过两种颜色的交替染色，在线性时间内完成判定。这一思想可以推广到更复杂的图论问题，如最大匹配、最小点覆盖等。掌握二分图的相关算法，是深入理解图论和网络流的基础。