C++ 检查可能的二分图

二分图定义

二分图因其独特的性质和在实际问题解决场景中的应用，在各个领域都具有重要意义。以下将对其关键性质、应用及其在不同领域的影响进行探讨。

二分图的性质

2-可着色性：二分图的一个基本性质是其2-可着色性。这意味着图的顶点可以分成两个不相交的集合（通常表示为 U 和 V），使得任意两个相邻顶点的颜色不同。这一性质简化了各种图算法和问题解决方法，因为检查图是否为二分图可以归结为一个简单的着色问题。

无奇数长度环：二分图的另一个定义特征是它们不包含奇数长度的环。这一性质与其2-可着色性直接相关：如果一个图包含奇数长度的环，那么它就不能被2-着色，而不会违反相邻顶点颜色不同的规则。

二分图的应用

二分图在不同学科中都有广泛的应用。

匹配问题：在工作分配、稳定婚姻和资源分配等领域，二分图用于模拟关系，其中每对元素都来自两个不同的集合。例如，在稳定婚姻问题中，每个男人和女人都可以表示为两个不相交集合中的顶点，边表示可接受的配对。

网络流：用于寻找网络最大流的算法通常利用二分图结构。二分性确保了流量可以从一个集合最优地路由到另一个集合，而不会发生冲突，从而最大化资源分配和网络使用的效率。

调度问题：二分图用于调度可分为两组的任务，确保任务的分配或执行方式能够最大程度地减少冲突并优化资源利用率。

图着色：许多复杂的图问题都可以归结为检查图是否为2-可着色。这种归约通过为处理具有连接约束的顶点着色提供结构化方法，简化了问题解决和算法设计。

方法一：使用广度优先搜索 (BFS)

广度优先搜索 (BFS) 方法通过尝试使用两种颜色为图着色来检查二分性。它首先将所有顶点初始化为未着色状态。从任何未访问的顶点开始，BFS 逐层探索图：为当前顶点着一种颜色，为其邻居着相反的颜色。

如果 BFS 遇到一个顶点与其邻居具有相同颜色的情况，则该图不是二分图。此方法确保所有顶点都经过检查以符合二分图性质，从而确认该图是否确实可以分割成两个不相交的集合，其中同一集合内的任意两个顶点都不相邻。BFS 算法能有效处理连通图和非连通图，通过其层层递进的探索策略确保对二分性的全面验证。

用于检查二分性的 BFS 方法在时间和空间上都具有效率，适合各种图相关问题。其在线性复杂度和顶点数与边数相关，确保了它在大图和稀疏图上表现良好，是确定图是否可分割的可靠方法。

程序

输出

 
Enter number of nodes and edges: 4 3
Enter the edges (u v) where 0 <= u, v < 4:
1 2
2 3
3
3 4 
The adjacency list of the graph is:
Vertex 0:
Vertex 1: 2
Vertex 2: 1 3
Vertex 3: 2 3 3
The graph cannot be bipartitioned.

说明

• 图的表示

在提供的实现中，图使用邻接表表示。这是表示稀疏图的一种常见且有效的方法。邻接表存储在向量的向量中，其中每个向量对应一个顶点并包含其相邻顶点的列表。

• 颜色数组

该算法使用颜色数组来跟踪分配给每个顶点的颜色。此数组的大小与图中顶点的数量相同。最初，所有顶点都未着色，用 -1 表示。两种可能的颜色是 0 和 1。

• 处理非连通图

该算法遍历图的所有顶点以处理非连通分量。如果发现一个顶点未着色，则从该顶点开始BFS 遍历。这确保了图的每个分量都经过二分性检查。

• 广度优先搜索 (BFS)

BFS 遍历使用队列实现。起始顶点被入队并着色为 0。主要的 BFS 循环一直持续到队列为空。

出队一个顶点：队列前端的顶点被出队进行处理。

处理相邻顶点：对于出队顶点的每个相邻顶点（邻居）

未着色的邻居：如果邻居未着色，则为其着与当前顶点相反的颜色，然后将其入队。

已着色的邻居：如果邻居已着色且颜色与当前顶点相同，则表示存在冲突，即图不是二分图。函数立即返回 false。

如果在 BFS 遍历过程中未发现冲突，则图是二分图，函数返回 true。

• 输入和输出函数

为了方便用户交互，代码包含了从用户输入读取图的函数以及打印图的邻接表格式的函数。这些辅助函数确保图被正确构建，并清晰地可视化其结构。

读取图：readGraph 函数提示用户输入顶点和边的数量。之后，它读取代表边的整数对，并相应地构建邻接表。

打印图：printGraph 函数输出邻接表，显示每个顶点及其相邻顶点。这有助于验证输入并理解图的结构。

• 主函数

main 函数作为程序的入口点。它执行以下步骤：

输入：它提示用户输入顶点和边的数量，然后读取图。

图可视化：调用 printGraph 函数显示图的邻接表。

二分性检查：调用 isBipartiteBFS 函数检查图是否为二分图。

输出：输出结果，指示图是否可以二分。

复杂度分析

时间复杂度

BFS 方法正好处理图中的每个顶点和边一次。以下是详细的分析：

初始化

初始化颜色数组需要O(n) 时间，其中 n 是顶点的数量。这是因为每个顶点都被赋予了初始颜色值 -1。

外循环

外层循环遍历所有顶点以处理非连通图。在最坏的情况下，此循环运行 n 次，但 BFS 仅从未着色的顶点开始。此循环的总体复杂度为O(n)。

广度优先搜索 (BFS) 遍历

对于每个未着色的顶点，都会启动一次 BFS 遍历。在 BFS 遍历中：每个顶点被入队和出队一次，导致所有顶点的O(n) 操作。

每条边被检查正好两次（一次用于它连接的每个顶点），导致 O(m) 操作，其中 m 是边的数量。

处理节点

处理每个节点涉及检查其相邻顶点。此步骤确保在BFS 遍历期间扫描每个顶点的邻接表一次。

鉴于这些步骤，BFS 方法的总体时间复杂度为O(n+m)。这可以理解为：初始化和外层循环的贡献为 O(n)。

BFS 遍历正好处理每个顶点和边一次，贡献 O(n+m)。因此，总时间复杂度由 BFS 遍历主导，结果为O(n+m)。

空间复杂度

BFS 方法的空间复杂度包括颜色数组、BFS 中使用的队列以及图的邻接表表示所需的空间。

颜色数组

大小为 n 的颜色数组存储分配给每个顶点的颜色。这需要O(n) 空间。

Queue

在最坏的情况下，队列可能存储图中的所有顶点，尤其是在图是单个连通分量时。因此，队列需要O(n) 空间。

邻接表

图的邻接表表示需要与顶点和边的数量成比例的空间。每个顶点都有一个邻接表，该表总共包含图的所有边。这导致O(n+m) 空间。

将这些组件结合起来，总体空间复杂度为O(n+m)。这可以细分为：

颜色数组需要 O(n)。队列需要 O(n)。邻接表需要 O(n+m)。

因此，总空间复杂度为O(n+m)。

方法二：使用深度优先搜索 (DFS)

深度优先搜索 (DFS) 方法是检查图是否为二分图的替代方法。与 BFS 方法一样，DFS 方法尝试使用两种颜色为图着色。目标是确保没有两个相邻顶点具有相同的颜色。这是通过递归（或使用堆栈进行迭代）遍历图并分配颜色来实现的，使得相邻顶点获得不同的颜色。

用于检查二分性的 DFS 方法类似于 BFS，但使用了递归或基于堆栈的遍历方法。基本思想保持不变：尝试使用两种颜色为图着色，以便没有两个相邻顶点具有相同的颜色。此方法特别有助于通过递归探索来理解图的连通性和结构。

程序

输出

 
Enter number of nodes and edges: 4 4
Enter the edges (u v) where 0 <= u, v < 4:
0 1
1 2 
2 3
3 0
The adjacency list of the graph is:
Vertex 0: 1 3
Vertex 1: 0 2
Vertex 2: 1 3
Vertex 3: 2 0
The graph can be bipartitioned.

说明

DFS 方法提供了一种直观且有效的方式来确定图是否可以进行二分。它利用递归或显式堆栈来深入探索顶点及其邻居，同时维护有关已访问顶点及其分配颜色的状态信息。

此方法非常适合处理连通图和非连通图，并确保所有分量都经过二分性检查。通过保持图表示的清晰度并利用堆栈进行迭代加深，DFS 方法有效地管理了图遍历的复杂性，为各种应用中的二分图检查提供了可靠的工具。

• 图表示和初始化

图使用邻接表表示，其中每个顶点维护其相邻顶点的列表。这种表示对稀疏图很有效，并且易于遍历和操作图数据。

使用颜色数组来促进二分性检查。此数组跟踪分配给每个顶点的颜色。最初，所有顶点都标记为颜色 -1，表示它们尚未着色。它确保我们可以区分未访问的顶点和已访问但尚未着色的顶点。

• DFS 遍历方法

DFS 方法的核心在于递归函数 dfs，该函数从给定顶点开始，并尝试从该顶点开始为图着色。该函数接受当前顶点、颜色数组、图邻接表以及要分配的当前颜色等参数。

• DFS 函数 (dfs)

dfs 函数是递归的，并将当前顶点 node 作为参数。它首先将当前顶点分配给指定的currentColor。之后，它遍历当前顶点的所有相邻顶点（邻居）。

• 对于每个邻居

如果邻居未着色（color[neighbor] == -1），则递归调用 dfs 并使用相反的颜色（1 - currentColor）。如果邻居已着色且颜色与当前顶点相同（color[neighbor] == currentColor），则图不是二分图，函数返回 false。

如果所有邻居都成功着色而没有冲突，则函数返回 true，表示图的当前分量是二分图。

• 主二分性检查函数 (isBipartiteDFS)

isBipartiteDFS 函数遍历图的所有顶点。对于每个尚未着色的顶点（color[i] == -1），它会使用 dfs 函数启动 DFS 遍历。

如果任何DFS 遍历遇到冲突（即，发现颜色相同的相邻顶点），则函数立即返回 false。如果所有顶点都处理完毕而没有冲突，则函数返回 true，表示整个图是二分图。

• 输入和输出处理

代码包含从用户输入读取图的函数 (readGraph) 和打印图的邻接表表示的函数 (printGraph)。这些函数确保图被正确构建和可视化，有助于调试和验证。

复杂度分析

时间复杂度

用于检查图是否为二分图的深度优先搜索 (DFS) 方法涉及正好遍历图中的每个顶点和每条边一次。以下是时间复杂度的详细分析：

初始化

初始化颜色数组和其他必要的数据结构需要O(n) 时间，其中 n 是图中顶点的数量。

DFS 遍历

DFS 遍历从每个未着色的顶点开始。在最坏的情况下，此遍历可以覆盖图的所有顶点和边。每个顶点处理一次，对于每个顶点，其每条边恰好遍历一次。

因此，DFS 遍历的时间复杂度为O(n+m)，其中 m 是图中的边数。此复杂度源于每条边被访问两次（每条边的端点各一次）。

总体复杂度

考虑到初始化和 DFS 遍历，DFS 方法检查二分性的总体时间复杂度为O(n+m)。

空间复杂度

DFS 方法的空间复杂度涉及遍历期间使用的数据结构的内存。以下是空间复杂度的细分：

颜色数组

主要的耗空间数据结构是颜色数组，它存储分配给每个顶点的颜色。它需要O(n) 空间，其中 n 是顶点的数量。

DFS 堆栈（或递归堆栈）

在 DFS 遍历期间，将使用显式堆栈（如果使用迭代方法）或递归调用堆栈（如果使用递归）来维护遍历的当前状态。

在最坏情况下，如果图是单个连通分量，此堆栈可以包含所有顶点。因此，堆栈所需的空间在最坏情况下也可以是O(n)。

邻接表

图的邻接表表示需要O(n+m) 空间，其中 m 是边数。需要此空间来存储所有顶点及其各自的邻接表。

总体复杂度

将这些因素结合起来，DFS 方法的总体空间复杂度为 O(n+m)。