二分图判定与匹配

📌 核心概念

二分图：顶点可分为两个不相交集合，所有边的两个顶点分别属于不同集合。

判定方法：染色法（BFS/DFS） 最大匹配：匈牙利算法

🎯 经典应用

Go 代码

func isBipartite(graph [][]int) bool {
    n := len(graph)
    colors := make([]int, n)
    for i := range colors {
        colors[i] = -1
    }
 
    var dfs func(int, int) bool
    dfs = func(node, color int) bool {
        colors[node] = color
 
        for _, neighbor := range graph[node] {
            if colors[neighbor] == -1 {
                if !dfs(neighbor, 1-color) {
                    return false
                }
            } else if colors[neighbor] == color {
                return false
            }
        }
 
        return true
    }
 
    for i := 0; i < n; i++ {
        if colors[i] == -1 {
            if !dfs(i, 0) {
                return false
            }
        }
    }
 
    return true
}

🎯 经典题目

题目	LeetCode	方法
判断二分图	785	染色法
可能的二分法	886	染色法

---

返回：图算法