C++ 中确定二分图的方法

在 C++ 编程中，确定一个图是否为二分图是一个常见且重要的问题。二分图是一种特殊类型的图，其顶点可以被划分为两个不相交的集合，使得图中的每条边都连接这两个集合中的顶点。

一种常见的确定二分图的方法是使用深度优先搜索（Depth-First Search，简称 DFS）或广度优先搜索（Breadth-First Search，简称 BFS）结合染色的策略。

我们以深度优先搜索为例。为每个顶点设置一个初始颜色，比如 0 表示未染色。然后，从任意一个未染色的顶点开始进行深度优先搜索。在搜索过程中，将当前顶点染为 1 色，接着遍历其相邻顶点。对于相邻顶点，如果未染色，则染为与当前顶点不同的颜色（即 2 色），然后继续对相邻顶点进行深度优先搜索；如果相邻顶点已经染色且颜色与当前顶点相同，那么说明该图不是二分图，直接返回 false。

以下是一个使用深度优先搜索来判断二分图的 C++ 示例代码：

#include <iostream>
#include <vector>

// 用于表示图的邻接表
std::vector<std::vector<int>> graph;

// 用于存储顶点的颜色
std::vector<int> color;

// 深度优先搜索函数
bool dfs(int node, int c) {
    color[node] = c;

    for (int neighbor : graph[node]) {
        if (color[neighbor] == c) {
            return false;
        }
        if (color[neighbor] == 0 &&!dfs(neighbor, 3 - c)) {
            return false;
        }
    }

    return true;
}

// 判断是否为二分图的函数
bool isBipartite() {
    for (int i = 0; i < graph.size(); ++i) {
        if (color[i] == 0 &&!dfs(i, 1)) {
            return false;
        }
    }
    return true;
}

int main() {
    // 构建图
    graph = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};

    color.resize(graph.size(), 0);

    if (isBipartite()) {
        std::cout << "该图是二分图" << std::endl;
    } else {
        std::cout << "该图不是二分图" << std::endl;
    }

    return 0;
}

通过上述方法，我们能够在 C++ 中有效地确定一个给定的图是否为二分图。这种算法的时间复杂度通常为 O(V + E)，其中 V 是顶点的数量，E 是边的数量。

在实际应用中，二分图的判断常用于解决许多图相关的问题，如任务分配、资源分配等，具有重要的实际意义。