二分图

Question

下面是一个 BFS 算法来判断一个图是否是二分图：

function isGraphBipartite(node, graph, visited, distance) {
    const queue = [node];
    distance[node] = 0; //Initial node's distance to itself is 0

    while (queue.length > 0) {
        
        let curNode = queue.shift();
        visited[curNode] = true; 
        
        for (let neighbor of graph[curNode]) {

            
            if(!visited[neighbor]) {
                visited[neighbor] = true;
                distance[neighbor] = distance[curNode] + 1;
                queue.push(neighbor);
            } else {
                if (distance[neighbor] === distance[curNode]) return false; //KEY LINE
            }
        }
    }
    return true;
}

var isBipartite = function(graph) {
    let visited = {};
    let distance = {};

    for (let vertex = 0; vertex < graph.length; vertex++) { 
        if(!visited[vertex]) { 
            if (!isGraphBipartite(vertex, graph, visited, distance)) return false;
        }
    }
    return true;
};

我知道有效的双字母不能有奇数循环。我也知道图中存在相同级别的交叉边会使它作为双图无效。

是否有某种数学公式 intuition/explanation/rationale where if (distance[neighbor] === distance[curNode]), 这意味着有一个相同级别的交叉边以某种方式生成一个奇数循环？

Answer 1

如果节点 A 和 B 到根的路径长度相同，则它们与这些路径分叉处的节点的距离相同。如果A和B也是邻居，那么他们形成一个长度为2*distance+1的顶点的循环，这是奇数。

因此，与根距离相同的节点之间的任何边表明该图不是二分图。此外，由于相邻节点与根的距离最多相差 1，因此仅这些边表示奇数循环。当这些边不存在时，所有边将偶数 BFS 层中的节点连接到奇数 BFS 层中的节点，这就是二分分区。

二分图

Bipartite Graphs

graph

bipartite

graph-algorithm

data-structures