如何在 C++ 中确定一个二分图？

译者 | 朱钢

审校 | 梁策 孙淑娟

确定一个图形是中确否是二分图的问题不仅对面试非常重要，也有助于解决现实生活中的分图问题。比如，中确在举办足球联赛时，分图用它来看看哪些球员为哪些组织效过力。中确这样的分图例子比比皆是，本文也将就这一问题重点讨论。中确

为了解决这个问题，分图我们需要深入了解二分图、中确图着色、分图BFS、中确DFS 和循环无环图的分图知识。首先来看看定义：

循环图和非循环图：具有偶数个循环，中确以循环方式闭合的分图图称为循环图。而如果图中没有闭合形状，中确则称为非循环图。如果在无向图中有一个封闭的形状，它肯定是一个循环，而对于有向图，就可能不是这样。比如在下图中：

该图显示，具有闭合形状的无向图将是企商汇循环的，但有向图既可能循环也可能不循环。对于循环的有向图，边的方向应以循环方式包围。

可着色图：如果我们只有两种颜色(比如红色和蓝色)，并且我们可以为图的每个顶点着色，从而让图形的每条边的两个顶点的颜色不同，那么该图是 2-colorable (2-可着色)。简单来说，我们可以说交替的顶点应该有相同的颜色，或者两个相邻的顶点不应该有相同的颜色。

在上图中，第一个图是 2-colorable ，因为没有两个相邻顶点颜色相同。 在第二个图中，相邻的顶点 V1 和 V5 具有相同的颜色，因此 Graph 不是 2-colorable。云南idc服务商

从上图中，我们可以看到边数为偶数的循环图是 2-colorable 的，而边数为奇数的循环图不是 2-colorable 的。对于所有具有循环的图都是如此，因为在偶数循环(具有偶数边/顶点的循环)的情况下，顶点被分成对(一个顶点是红色，另一个是蓝色)，但是当我们有一个奇数大小的循环(具有奇数边/顶点的循环)时，一个顶点将被省略。

此外，对于具有多个循环的图要成为 2-colorable ，所有循环必须是偶数大小的循环。 如下图所示：

由于存在奇数循环，因此它是非二分图。源码库

上文介绍了循环图的可着色性质。那么非循环图呢?让我们看一些如下所示的示例：

这些图显示了各种非循环图，它们都是 2-colorable。

通常，所有非循环图都是 2-colorable 的。这背后的原因很简单。当一个图是循环时，在两个方向上都有相邻的顶点，当存在一个奇数大小的循环时，这些边之一的相邻顶点恰好是相同的颜色。

在无环图中，可能有两个方向的相邻顶点，但无环图中的方向往往线性相同。因此，我们可以说所有无环图都是 2-colorable。

所以，最后我们可以根据观察结果设置一些规则，让图形是 2-colorable：

如果一个图形是循环的，那么它是一个 2-colorable 图，它的所有循环都应该是偶数大小的循环。对上述观点进行一些拓展，哪怕只有一个奇数循环的循环图都将是非2-colorable 的。所有的非循环图都是 2-colorable。

现在，来谈谈我们的问题，即二分图。

二分图：

如果一个图的顶点可以分为两个这样的子集，它们是互斥(交集应该是空集)且相互穷举的(联合是所有顶点的集合)，并且边跨两个集合而不是在同一个集合内， 那么就说该图形是二分的。

二分图示例

非二分图示例

如我们所见，有一条边 V0-V4，其顶点位于同一集合中。你可以尝试创建任何可能的集合，但总是会找到同一集合内的边。因此，上图是非二分图 。

那么，通过观察上面的例子，你是否获得了一些启发呢?我们可以看到，第一个二分图也是 2-colorable 。此外，第二张图不是二分图，也不是 2-colorable 。因此，我们可以说二分图只不过是一个 2-colorable 图。

快速观察：由于具有奇数循环的图永远不会 2-colorable，因此可以说它永远不会是二分的。此外，如果图中有多个循环，则所有循环都必须是偶数循环(边数应该是偶数)才能使图成为二分图。如果一个图是非循环的(没有循环)，它肯定是二分的，因为它总是 2-colorable。如果一个图形有一个自循环 ，即一个图的顶点有一条边，那么它是非二分的，因为我们不能用两种不同的颜色为同一个顶点着色。

方法 1：为每个顶点分配颜色 (BFS)

问题陈述：必须确定给我们的图是否是二分的。

思维过程：上文已经研究过，2-colorable图是二分图。那么，让我们来给图形的每个顶点逐一着色，注意相邻的顶点不应该有相同的颜色。如果我们能够使用 2-colors成功地为图形着色，则图形将是二分的，否则不是。

算法：选择两个数字，描述要在输入图的顶点上完成的两种颜色。(假设数字是 1 和 2，未着色的顶点将由数字 0 表示)选择任何顶点作为图形的源顶点，并使用第一种颜色(即 1)对其进行着色。用第二种颜色为源顶点的所有相邻顶点着色，并用第一种颜色再次着色它们的相邻顶点，依此类推。(使用大小等于顶点数的颜色数组来保持哪个顶点具有什么颜色)。当我们要为一个顶点着色时，这样做是为了知道所有相邻顶点的颜色。如果所有的顶点都被成功着色而不违反2-colorable的图形要求，即如果我们没有出现2个相邻顶点用相同颜色着色的情况，那么它是二分的，否则只要找到一个顶点与相邻顶点有相同的颜色，那么返回 false， 表示该图不是二分图。另外，不要忘记图形是可以不连接的。因此，对图形的每个组件都执行此过程。

使用邻接矩阵作为输入的 C++ 代码

输入：图将以大小为 V x V 的邻接矩阵的形式输入给我们，其中 V 是图中的顶点数。它将是一个二进制矩阵，描述是否存在从顶点 V1 到另一个V2 的边。输入示例如下所示：

上图描绘了输入矩阵的示例。从 V0 到 V1 有一条边，因此我们有 Matrix[V0][V1] = 1 等等。

#include

using namespace std;

// colors:

// red = 1 and blue = 2;

bool isBipartiteHelper(int graph[100][100],int vertices, int src, vectorcolors) {

//coloring the source vertex red

colors[src] = 1;

// queue needed for BFS Traversal

queueque;

que.push(src);

while(!que.empty()) {

int front = que.front();

que.pop();

// If self Loop exists, then adjacency matrix

// will have 1 in the diagonal element

// and we have to return false in case of adjacency matrix

if(graph[front][front] == 1) return false;

for(int i=0;i

// edge exists and the adjacent vertex i is uncolored

if(graph[front][i] == 1 && colors[i] == 0) {

if(colors[front] == 1) colors[i] = 2; //color alternatively

else colors[i] = 1;

que.push(i);

} else if(graph[front][i] == 1 && colors[i] == colors[front]) { //edge exists and same color of adj vertex

return false;

}

}

}

return true; //all vertices of this component can be colored

// as per the rule of 2-colorable graph

}

bool isBiPartite(int Graph[100][100], int vertices) {

vectorcolors(vertices,0);

// Assume i to be a source vertex of current component

for(int i=0;i

// If i is uncolored

if(colors[i] == 0) {

// if any component is non bipartite, graph is also non bipartite

if(isBipartiteHelper(Graph,vertices,i,colors) == false) return false;

}

}

return true; //if all the components are bipartite then the entire graph is bipartite

}

int main() {

int vertices;

cin>>vertices;

int Graph[100][100];

for(int i=0;i

for(int j=0;j

cin >> Graph[i][j];

}

}

cout<<"The given graph ";

if(isBiPartite(Graph,vertices) == true)

cout<<"is bipartite\n";

else cout<<"is not bipartite\n";

return 0;

}

用 ​​InterviewBit ​​试试代码

输出：

方法分析：

该代码涵盖了具有自循环图的极端情况，但该代码不包括具有平行边图的情况，即同一对顶点之间的多条边，如下所示：

该图涵盖了图形划分为多个未连接组件的情况。

时间复杂度：时间复杂度为 O(V2)，因为我们正在遍历大小为 V x V 的邻接矩阵。

空间复杂度：邻接矩阵使用 O(V2) 空间表示图，但这不是空间复杂度。除此之外，O(V) 空间是用于存储每个顶点颜色的辅助空间。

(V 是上述复杂度中的顶点数。)

现在让我们看一下上述相同的方法的优化版。为了优化解决方案，我们将使用邻接列表代替矩阵作为输入。

使用邻接表的 C++ 代码

输入：输入将是一个邻接列表。现在，用户必须以源-目的地(source-destination)顶点对的形式输入所有边。此外，在这种情况下，我们认为图是无向的。因此，如果用户输入一条边 V0-V1 并认为有一条从 V0 到 V1 的边，那么由于考虑到图是无向的，也会有一条从 V1 到 V0 的边自动插入。

#include

using namespace std;

// colors: red = 1 and blue = 2

bool isGraphBipartite(vectorlist[], int vertices) {

// make a vector for storing

// colors of all the vertices

// Since all the vertices are

// initially uncolored,

// fill the vector with 0s

vectorcolors(vertices,0);

// queue of pair will be made

// as we will store the vertex

// along with its color

queue> que;

// The same logic for non connected components

// that we did using adjacency matrix

// will be applied here

for(int i=0;i

// check whether the taken

// source vertex for current

// component is not colored

// If found uncolored

// apply BFS on the component

if(colors[i] == 0) {

pairsrcVertex;

srcVertex.first = i;

srcVertex.second = 1;

que.push(srcVertex);

colors[i] = 1; //color the source vertex of current component red

// BFS on current component of the graph

while(!que.empty()) {

pairfront = que.front();

que.pop();

int currVertex = front.first;

int currVertexColor = front.second;

// traversing adjacent vertices of current vertex

for(int adjVtx: list[currVertex]) {

if(colors[adjVtx] == currVertexColor) return false;

else if(colors[adjVtx] == 0) {

if(currVertexColor == 1) colors[adjVtx] = 2; //coloring alternatively

else colors[adjVtx] = 1;

pairadjPair;

adjPair.first = adjVtx;

adjPair.second = colors[adjVtx];

que.push(adjPair);

}

}

}

}

}

return true;

}

int main() {

int vertices, edges;

cin>>vertices>>edges;

vectorlist[vertices];

for(int i=0;i

int sv,av;

cin>>sv>>av;

list[sv].push_back(av);

list[av].push_back(sv);

}

cout<<"The given graph is";

if(isGraphBipartite(list,vertices) == true)

cout<<" bipartite\n";

else cout<<" not bipartite\n";

return 0;

}输出：

方法分析：

此代码仅使用邻接列表而不是矩阵。此代码涵盖了自循环情况，以及多个未连接组件的情况。但是，没有涵盖具有平行边图的情况。

时间复杂度：如上所述，时间复杂度为 O(V+E)。

空间复杂度：使用邻接矩阵来存储图形，但辅助空间是 O(V)，即存储每个顶点的颜色。

跟进此方法：尝试通过相同的方法解决此问题，即为所有顶点着色，但是使用 DFS(递归)而不是 BFS。这意味着你必须应用相同的方法为图形着色，但我们使用了 BFS 来做到这一点，也建议你用递归 (DFS) 来尝试一下。

方法 2：访问级别方法 (BFS)

算法：该方法基于检查图中的循环。如果图是非循环的，我们将返回 true，因为非循环图是 2-colorable 的，也就是二分的。但如果存在循环，我们需要找出它的长度是奇数还是偶数。如果循环长度为奇数，则将在欧拉树(递归树)中的不同级别上再次访问相同的顶点，而如果循环长度为偶数，则将在同一级别上再次访问相同的顶点。

如上所示，我们正在使用 BFS 并探索源顶点的所有未访问的相邻顶点。在第一个图的情况下，即具有奇数循环的图，V4 在同一 BFS 树的第 2 层和第 3 层上被访问，而在具有偶数循环的图的情况下，再次访问的顶点(V3)在同一级别访问。因此，在奇数长度循环的情况下，确定循环的顶点将处于两个不同的级别，而在偶数长度循环的情况下，它将处于同一级别。

因此，一旦我们得到一个重复自身的顶点(它将发生在循环图中)，我们就检查该顶点最后一次访问的时间，以及它的级别是否相同。同样，不要忘记该图可以分为多个未连接的组件。因此，BFS 将应用于每个组件。

第二种方法的 C++ 代码

输入：输入将是一个邻接列表。现在，用户必须以source-destination顶点对的形式输入所有边。此外，在这种情况下，我们认为图是无向的。因此，如果用户输入一条边 V0-V1 并认为有一条从 V0 到 V1 的边，那么由于考虑到图是无向的，也会有一条从 V1 到 V0 的边自动插入。

思考过程：在应用 BFS 时，我们不只是将顶点推送到队列中，而是将其与正在访问的 Level 一起推送，并且标记为已访问。因此，当我们再次遇到相同的顶点时，我们将看到它之前访问过的级别(Level)是什么。如果级别与当前访问的相同，则图的分量是偶数循环的，那么该分量是二分的，但整个图不是。为了使整个图是二分的，所有组件都应该是非循环的或偶数长度循环的。

#include

using namespace std;

bool isComponentBipartite(vectorlist[],int src,vector&visited) {

queue> que; //this pair corresponds to vertex -> level

// which means vertex and the level in which

// it appeared in the recursion tree

// of BFS

pairsrcPair;

srcPair.first = src;

srcPair.second = 0; //initially source is at 0 level in recursion tree

que.push(srcPair);

// Apply BFS

while(!que.empty()) {

pairfront = que.front();

que.pop();

if(visited[front.first] != -1) { //if the vertex (i.e. front.first) is already visited

//since the vertex is already visited, check if the levels are not same

if(visited[front.first] != front.second) {

return false; //odd length cycle detected

}

} else {

visited[front.first] = front.second;

}

//now visit all the adjacent vertices

for(int adj : list[front.first]) {

if(visited[adj] == -1) {

pairadjPair;

adjPair.first = adj;

adjPair.second = front.second + 1;

que.push(adjPair);

}

}

}

return true; //either no cycle detected or all cycles were even length

}

int main() {

int vertices,edges;

cin>>vertices>>edges;

vectorlist[vertices];

for(int i=0;i

int sv;

int dv;

cin>>sv>>dv;

//since non-directed graph, edges will be bi-directional

list[sv].push_back(dv);

list[dv].push_back(sv);

}

//initially no vertex is visited and hence all are at level -1

vectorvisited(vertices,-1);

//for non connected components as we need to check whether every component is bipartite or not

for(int i=0;i

if(visited[i] == -1){

bool ans=isComponentBipartite(list,i,visited);

if(ans == false){

cout<<"The graph is not bipartite";

return 0;

}

}

}

cout<<"Graph is bipartite";

return 0;

}输出：

简要说明：此代码不涵盖图形划分为多个组件的情况。

时间复杂度：由于我们使用邻接表进行图遍历(BFS)，时间复杂度为 O(V + E)。这与着色方法相同，即如果我们使用邻接矩阵，复杂度将是 O(V2)。所以，我们这次直接使用邻接表来优化方案。

空间复杂度：在 BFS 中，我们使用的队列最多可以存储所有 V 个顶点。因此，空间复杂度可以称为 O(V)。 O(V + E) 是邻接表的空间，但不是输入空间的空间复杂度。

结论

我们学习了两种不同的方法来检测图形是否为二分图。你可以选自己顺手的方法，因为两者在复杂性(时间和空间)方面是相同的。不过，由于图着色方法更容易理解诠释，在显示二分图与 2-colorable 图的关系时也更清晰，所以这种方法也更常见。

译者介绍

朱钢，社区编辑，2021年IT影响力专家博主，阿里云专家博主，2019年CSDN博客之星20强，2020年腾讯云+社区优秀作者，11年一线开发经验，曾参与猎头服务网站架构设计，企业智能客服以及大型电子政务系统开发，主导某大型央企内部防泄密和电子文档安全监控系统的建设，目前在北京图伽健康从事医疗软件研发工作。

原文标题：​​How to Check if a Graph is Bipartite in C++​​，作者：Prashanth

很赞哦!（9871）