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

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

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

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

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

在上图中，第一个图是 2-colorable ，因为没有两个相邻顶点颜色相同。 在第二个图中，相邻的顶点 V1 和 V5 具有相同的颜色，因此 Graph 不是 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， 表示该图不是二分图。
• 另外，不要忘记图形是可以不连接的。因此，对图形的每个组件都执行此过程。

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

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

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

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

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

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

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

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

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

时间复杂度：如上所述，时间复杂度为 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)是什么。如果级别与当前访问的相同，则图的分量是偶数循环的，那么该分量是二分的，但整个图不是。为了使整个图是二分的，所有组件都应该是非循环的或偶数长度循环的。

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

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

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

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

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