这段代码有什么问题，它检查 2 个可着色图（二分图）

Question

我写了一段代码来检查给定的图是否是二分图，但不确定为什么一个代码有效而另一个无效。

以下无效，

bool dfs(int i, int color, vector<vector<int>> &graph) {
    if (visited[i] == -1) {
        visited[i] = color;
        for (int adj: graph[i])
            return dfs(adj, !color, graph);
    }
    return (visited[i] == color);
}
bool isBipartite(vector<vector<int>> &graph) {
    visited.assign(105, -1);
    for (int i = 0; i < graph.size(); i++) {
        if (visited[i] == -1)
            if (!dfs(i, 0, graph)) return false;
    }
    return true;
}
vector<int> visited;

但是当我把上面改成这个的时候

bool dfs(int i, int color, vector<vector<int>> &graph) {
    if (visited[i] == -1) {
        visited[i] = color;
        for (int adj: graph[i])
            if (!dfs(adj, !color, graph)) {
                return false;
            }
    }
    return (visited[i] == color);

}
bool isBipartite(vector<vector<int>> &graph) {
    visited.assign(105, -1);
    for (int i = 0; i < graph.size(); i++) {
        if (visited[i] == -1)
            if (!dfs(i, 0, graph)) return false;
    }
    return true;
}
vector<int> visited;

有效，谁能告诉我为什么？请注意，dfs 函数中只有第 5 行和第 6 行发生了更改。

这两个代码不应该工作吗，因为它们似乎工作相同？

Answer 1

在您的第一个代码片段中，

        for (int adj: graph[i])
            return dfs(adj, !color, graph);

您在 for 循环的第一次迭代中返回。因此，对于每个节点，您只检查其邻居之一，而忽略其余节点。

请注意，您的第二个代码段也不完全正确。你错过了节点没有邻居的情况，或者它的所有邻居都有正确的颜色：

bool dfs(int i, int color, vector<vector<int>> &graph) {
    if (visited[i] == -1) {
        visited[i] = color;
        for (int adj: graph[i])
            if (!dfs(adj, !color, graph)) {
                return false;
            }
        return true;
    }
    return (visited[i] == color);
}

这段代码有什么问题，它检查 2 个可着色图（二分图）

What's wrong with this code which checks for 2 colourable graph (bipartite)

algorithm

graph

bipartite