无向图节点二划分可行性验证及结果输出的线性时间算法求解

你要求的划分规则本质就是判断无向图是否为二分图（二部图），划分得到的两个子集就是二分图的两个部集。

采用BFS染色法实现，时间复杂度为O(V+E)，符合线性时间要求。

核心思路 #

用两种颜色对图中节点染色，要求所有相邻节点颜色不同，0色对应V1集合，1色对应V2集合。如果染色过程中没有出现冲突，即可得到符合要求的划分；如果出现相邻节点同色，说明图中存在奇数长度的环，无法完成划分。

具体步骤 #

• 初始化一个长度等于节点总数的染色数组，所有元素初始值设为-1，代表节点未被染色
• 遍历所有节点，对每个未染色的节点执行以下操作（处理非连通图场景）：
  • 将当前节点染为0，加入BFS队列
  • 依次弹出队列中的节点u，遍历u的所有邻接节点v：
    • 若v未染色，将v染为与u相反的颜色，加入队列
    • 若v已染色，且颜色与u相同，说明存在冲突，直接返回「不存在符合要求的划分」
• 所有节点染色完成无冲突后，将所有0色节点归入V1，1色节点归入V2，返回两个集合即可。

// 输入：无向图邻接表 adj，节点总数 n
// 输出：划分存在返回(V1, V2)，否则返回null
function getBipartition(adj, n) {
    const color = new Array(n).fill(-1);
    for (let i = 0; i < n; i++) {
        if (color[i] === -1) {
            const queue = [i];
            color[i] = 0;
            while (queue.length > 0) {
                const u = queue.shift();
                for (const v of adj[u]) {
                    if (color[v] === -1) {
                        color[v] = color[u] ^ 1;
                        queue.push(v);
                    } else if (color[v] === color[u]) {
                        return null;
                    }
                }
            }
        }
    }
    const V1 = [], V2 = [];
    for (let i = 0; i < n; i++) {
        color[i] === 0 ? V1.push(i) : V2.push(i);
    }
    return [V1, V2];
}

• 时间复杂度：每个节点仅入队一次，每条边会被两个端点各访问一次，总操作次数为O(V+E)，属于线性时间复杂度
• 空间复杂度：需要O(V)的空间存储染色数组和BFS队列，邻接表为输入不计入额外空间

内容的提问来源于stack exchange，提问作者mario