题目描述补充

给定一个无向图G = (V, E)，其中V是顶点集，E是边集。我们需要判断这个图是否可以被二分（也称为二部图或偶图）。在图论中，一个图如果顶点可以被划分为两个互不相交的集合A和B，使得图中的每一条边连接的两个顶点分别属于A和B（即图中没有边连接两个属于同一集合的顶点），则称该图为二分图。

示例

假设有以下图：

    A ---- B
   / \   / \
  C---D---E
   \ /   \ /
    F ---- G

此图可以被二分，例如，顶点集A = {A, C, E, G} 和 B = {B, D, F}。

解题思路

一种常见的方法是使用图的着色算法（也称为二分图判定算法），通常通过深度优先搜索（DFS）或广度优先搜索（BFS）来实现。我们可以尝试给每个顶点着色（通常是两种颜色，如0和1），并确保每条边的两个顶点颜色不同。

PHP 示例代码

<?php
function isBipartite($graph) {
    $n = count($graph);
    $color = array_fill(0, $n, -1); // 初始化颜色数组，-1表示未着色

    for ($i = 0; $i < $n; $i++) {
        if ($color[$i] == -1 && !dfs($graph, $i, 0, $color)) {
            return false; // 如果某个顶点不能正确着色，则不是二分图
        }
    }
    return true;
}

function dfs($graph, $v, $c, &$color) {
    $color[$v] = $c;
    foreach ($graph[$v] as $u) {
        if ($color[$u] == $c) {
            return false; // 发现相邻节点颜色相同，不是二分图
        }
        if ($color[$u] == -1 && !dfs($graph, $u, 1 - $c, $color)) {
            return false; // 递归地为相邻节点着色，并检查
        }
    }
    return true;
}

// 示例图的邻接表表示
$graph = [
    0 => [1, 2],
    1 => [0, 3, 4],
    2 => [0, 3, 5],
    3 => [1, 2, 4],
    4 => [1, 3, 5],
    5 => [2, 4]
];

// 调用函数并输出结果
if (isBipartite($graph)) {
    echo "该图是一个二分图。\n";
} else {
    echo "该图不是一个二分图。\n";
}
?>

Python 示例代码

def is_bipartite(graph):
    def dfs(node, color, colors):
        colors[node] = color
        for neighbor in graph[node]:
            if colors[neighbor] == color:
                return False
            if colors[neighbor] == -1 and not dfs(neighbor, 1 - color, colors):
                return False
        return True

    n = len(graph)
    colors = [-1] * n
    for i in range(n):
        if colors[i] == -1 and not dfs(i, 0, colors):
            return False
    return True

# 示例图的邻接表表示
graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 3, 5],
    3: [1, 2, 4],
    4: [1, 3, 5],
    5: [2, 4]
}

# 调用函数并输出结果
if is_bipartite(graph):
    print("该图是一个二分图。")
else:
    print("该图不是一个二分图。")

JavaScript 示例代码

function isBipartite(graph) {
    const n = graph.length;
    const colors = new Array(n).fill(-1); // -1 表示未着色

    function dfs(node, color) {
        colors[node] = color;
        for (let neighbor of graph[node]) {
            if (colors[neighbor] === color) return false;
            if (colors[neighbor] === -1 && !dfs(neighbor, 1 - color)) return false;
        }
        return true;
    }

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

// 示例图的邻接表表示
const graph = [
    [1, 2], [0, 3, 4], [0, 3, 5], [1, 2, 4], [1, 3, 5], [2, 4]
];

// 调用函数并输出结果
if (isBipartite(graph)) {
    console.log("该图是一个二分图。");
} else {
    console.log("该图不是一个二分图。");
}

码小课网站中有更多相关内容分享给大家学习，包括图论的其他算法和数据结构的高级应用。