检查给定图是否为二分图

2025年2月7日 | 阅读8分钟

引言

图论是计算机科学和数学的一个基础分支，它研究图，图是用于模拟对象之间成对关系的数学结构。二分图的概念是图论中的一个重要概念。确定给定图是否为二分图是图论中的一个常见问题，在调度、匹配和网络设计等众多实际应用中都有其用武之地。

理解二分图

二分图是一种图，其顶点可以划分为两个不相交的集合，使得同一集合内的任意两个顶点都不相邻。换句话说，二分图是可以使用两种颜色进行着色的图，使得任意两个相邻的顶点颜色不同。

数学上，图 G = (V, E) 是二分图当且仅当其顶点集 V 可以划分为两个不相交的集合 V1 和 V2，使得 E 中的每条边都连接 V1 中的一个顶点和 V2 中的一个顶点。

示例

让我们来看一个简单的例子来阐述这个概念。假设我们有以下图。

Check whether a given graph is Bipartite or not

我们可以先将顶点 A 涂成红色。然后，我们将它的邻居 B 和 C 涂成蓝色。最后，我们将顶点 D 涂成红色。检查后，我们发现顶点 B 和 D 是相邻的，并且颜色相同（红色），这违反了二分图的性质。因此，该图不是二分图。

检查图的二分性

要检查给定图是否为二分图，我们可以使用流行的图遍历算法，例如深度优先搜索 (DFS) 或广度优先搜索 (BFS)。基本思想是在遍历过程中为顶点分配颜色并检查是否存在冲突。如果出现冲突（即相邻顶点的颜色与当前顶点相同），则该图不是二分图；否则，它是二分图。

检查二分性的算法

广度优先搜索 (BFS)

检查二分性最直接的方法之一是使用 BFS 遍历。该思想是在 BFS 遍历过程中遇到的顶点时，为它们交替分配颜色（假设为 0 和 1）。如果在遍历的任何时候，发现一条边连接了两个相同颜色的顶点，则该图不是二分图。

以下是该算法的简要概述

选择任意一个顶点 v 开始遍历。
为顶点 v 分配颜色 0。对于 v 的每个相邻顶点 u，为其分配相反的颜色（即，如果 v 是 0，则 u 是 1，反之亦然）。
重复步骤 2 和 3，为所有顶点赋值，确保不分配冲突的颜色。
如果在任何时候出现冲突（即，相邻顶点的颜色与当前顶点相同），则该图不是二分图。
如果在遍历过程中没有遇到冲突，则该图是二分图。

实施

现在，让我们来实现上述算法

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool isBipartite(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> color(n, -1); // Initialize all vertices with color -1 (unassigned)
    queue<int> q;   
    for (int i = 0; i < n; ++i) {
        if (color[i] == -1) {
            color[i] = 0; // Assign color 0 to start BFS traversal
            q.push(i);          
            while (!q.empty()) {
                int u = q.front();
                q.pop();               
                for (int v : graph[u]) {
                    if (color[v] == -1) {
                        color[v] = 1 - color[u]; // Assign opposite color
                        q.push(v);
                    } else if (color[v] == color[u]) {
                        return false; // Conflict found, not bipartite
                    }
                }
            }
        }
    }
    return true; // No conflicts found, bipartite
}
int main() {
    // Example graph representation (adjacency list)
    vector<vector<int>> graph = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};   
    if (isBipartite(graph)) {
        cout << "The given graph is bipartite.\n";
    } else {
        cout << "The given graph is not bipartite.\n";
    }    
    return 0;
}

程序输出

说明

程序通过定义一个名为 isBipartite 的函数来开始，该函数接受一个 2D 向量 graph 的引用，表示输入图的邻接列表。此函数返回一个布尔值，指示图是否为二分图。
在 isBipartite 函数中，它初始化一个大小为 n 的向量 color，其中 n 是图中顶点的数量。color 向量的每个元素表示分配给相应顶点的颜色。
最初，所有顶点都被分配颜色 -1，表示它们未被分配。它还初始化一个队列 q 用于执行广度优先搜索 (BFS)。
然后，该函数遍历图中的每个顶点。如果一个顶点的颜色是 -1（即未分配），则为其分配颜色 0 并将其推入队列以开始 BFS 遍历。
在 BFS 遍历过程中，它检查当前顶点的每个邻居。如果邻居未分配颜色（color[v] == -1），则为其分配与当前顶点相反的颜色并将其推入队列。
如果邻居已分配颜色，并且与当前顶点的颜色相同（color[v] == color[u]），则表示存在冲突，表明该图不是二分图。
从每个未访问的顶点进行 BFS 遍历后，如果没有发现冲突，则函数返回 true，表示该图是二分图。否则，它返回 false。
在 main 函数中，创建了一个表示为邻接列表的示例图。然后调用 isBipartite 函数来检查图是否为二分图，并相应地打印结果。

深度优先搜索 (DFS)

检查二分性的另一种方法涉及 DFS 遍历。与 BFS 方法类似，我们交替地为顶点分配颜色。如果在 DFS 遍历过程中，我们遇到连接两个相同颜色顶点的边，则该图不是二分图。

以下是基于 DFS 的算法的高层概述

从任何任意顶点开始 DFS 遍历。
为起始顶点分配颜色 0。
递归遍历其邻居，并为每个邻居分配相反的颜色。
对所有未访问的顶点重复此过程，确保相邻顶点具有不同的颜色。
如果在任何时候，我们发现同一颜色顶点之间的边，则该图不是二分图。

实施

现在，让我们来实现上述算法

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// Function to check if the graph is bipartite using DFS
bool isBipartiteDFS(int node, vector<vector<int>>& graph, vector<int>& colors) {
    stack<int> st;
    st.push(node);
    colors[node] = 0; // Assign color 0 to the starting node
    while (!st.empty()) {
        int currNode = st.top();
        st.pop();
        for (int neighbor : graph[currNode]) {
            if (colors[neighbor] == -1) { // If neighbor has not been visited
                colors[neighbor] = 1 - colors[currNode]; // Assign opposite color to neighbor
                st.push(neighbor);
            } else if (colors[neighbor] == colors[currNode]) {
                // If the neighbor has the same color as the current node, not bipartite
                return false;
            }
            // Else, the neighbor has already been visited with a different color, continue
        }
    }
    return true;
}
// Function to check bipartiteness of the graph
bool checkBipartite(vector<vector<int>>& graph, int numNodes) {
    vector<int> colors(numNodes, -1); // Array to store colors of nodes (-1 represents unvisited)
    for (int i = 0; i < numNodes; ++i) {
        if (colors[i] == -1) {
            if (!isBipartiteDFS(i, graph, colors)) {
                return false; // If any component is not bipartite, return false
            }
        }
    }
    return true; // If all components are bipartite, return true
}
int main() {
    int numNodes, numEdges;
    cout << "Enter the number of nodes and edges: ";
    cin >> numNodes >> numEdges;
    vector<vector<int>> graph(numNodes); // Adjacency list representation of the graph
    cout << "Enter the edges (node1 node2):" << endl;
    for (int i = 0; i < numEdges; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u); // For undirected graph
    }
    if (checkBipartite(graph, numNodes)) {
        cout << "The graph is bipartite." << endl;
    } else {
        cout << "The graph is not bipartite." << endl;
    }
    return 0;
}

程序输出

说明

程序以 main() 函数开始，在该函数中，它提示用户输入图中节点的数量和边的数量。
然后，它使用向量的向量（graph）创建图的邻接列表表示。此向量的每个元素代表一个节点，每个节点包含其相邻节点的列表。
接下来，程序调用 checkBipartite() 函数，将图和节点数量作为参数传递。在 checkBipartite() 内部，它用 -1 初始化一个 colors 向量，表示未访问的节点。
然后，它遍历图中的所有节点。对于每个未访问的节点，它调用 isBipartiteDFS() 函数，传递节点、图和 colors。
isBipartiteDFS() 函数从给定的节点开始执行 DFS 遍历。它初始化一个堆栈来迭代地执行 DFS。
对于堆栈中的每个节点，它会分配一个颜色（0 或 1）并探索其邻居。如果一个邻居未访问，它会为其分配相反的颜色并将其推入堆栈。
如果一个邻居已被访问并且与当前节点具有相同的颜色，则返回 false，表示图不是二分图。如果所有节点都被访问并且没有发现冲突的颜色，则返回 true，表示图是二分图。
最后，根据 checkBipartite() 的返回值，main() 函数打印图是否为二分图。如果是二分图，则打印“The graph is bipartite”，否则打印“The graph is not bipartite”。

时间复杂度分析

深度优先搜索 (DFS)

DFS 的时间复杂度为 O(V + E)，其中 V 是图中顶点的数量，E 是边的数量。
对于每个顶点，我们只遍历其邻接列表一次。
在最坏的情况下，我们可能需要遍历图的所有顶点和边。

广度优先搜索 (BFS)

BFS 的时间复杂度也为 O(V + E)，其中 V 是图中顶点的数量，E 是边的数量。
与 DFS 类似，对于每个顶点，我们只遍历其邻接列表一次。
在最坏的情况下，我们可能需要遍历图的所有顶点和边。

空间复杂度分析

深度优先搜索 (DFS)

DFS 的空间复杂度为 O(V)，用于维护颜色数组，以及 O(H)，用于调用堆栈，其中 H 是递归树的最大高度。
在最坏的情况下，当图是完全图时，H 可以是 O(V)，导致空间复杂度为 O(V)。

广度优先搜索 (BFS)

BFS 的空间复杂度为 O(V)，用于维护颜色数组和队列。
在最坏的情况下，当所有顶点都被推入队列时，队列大小可以为 O(V)，导致空间复杂度为 O(V)。

实际应用

二分图的概念在各种实际场景中都有应用，例如：

调度： 对任务和资源进行建模，其中某些任务需要特定资源，并且共享同一资源的两项任务不能同时安排。
网络路由： 确保不同网络之间的通信不会导致冲突或回路。
社交网络： 分析个人之间的关系，其中二分图可以表示用户和组之间的连接。
推荐系统： 根据用户偏好和项目特征向用户推荐项目，其中二分图可以表示用户-项目交互。

结论

总之，二分图是图论中的一个基本概念，在包括计算机科学和数学在内的各个领域都起着至关重要的作用。深度优先搜索 (DFS) 和广度优先搜索 (BFS) 等算法提供了确定图的二分性的有效方法，从而能够解决调度、网络设计和推荐系统等现实世界问题。理解和利用二分图为各种领域提供了宝贵的见解和解决方案，使其成为图论理论和实践应用中的基石。

下一个主题Connect-n-ropes-with-minimum-cost

检查给定图是否为二分图

引言

理解二分图

示例