algorithm - 检查图是否是二分的以及添加每条新边

Question

给定图中边的多个输入，例如（第一行是连接数）：

4
1 2
2 3
5 6
1 5

我必须在每次输入后检查图形是否仍然是二分的，如果图是非二分的，我们就会中断。我认为这是一些图形着色问题，但我无法实现它，请通过提供一些算法来帮助我。

标签： algorithmdata-structuresgraph

Answer 1

如果您可以找到该图的两种颜色，则该图是二分图。这很容易实现，因为不涉及回溯；对于每个连续的节点，只有一种颜色可用，如果该颜色不可能，因为其中一个邻居已经具有该颜色，则该图不是二分图。

例如，您可以将其实现为深度优先搜索，分别跟踪具有颜色 A 和颜色 B 的两个节点集。每次展开新节点时，都会切换颜色，如果该节点应该是 A 色，但已经在 B 集中，则该图不是二分图。

但是，您的情况似乎有点不同，在添加每个单独的边后检查图形是否是二分的。您仍然可以在每次迭代中对整个图运行 DFS，但这可能太慢了。

相反，为每个（仍然）断开的子图跟踪具有颜色 A 和颜色 B 的节点的两组。因此，当您添加边缘时(x, y)：

• 检查子图x和y所属（使用某种地图/字典）
• 如果都不属于子图，则开始一个新的子图
• 如果一个属于子图，但另一个尚未在图中，则为另一个节点赋予与已包含节点相反的颜色
• 如果两者都属于不同的子图，则将子图合并为一个（合并颜色集）；这可能需要翻转其中一个图表的颜色，以便x最终y不会得到相同的颜色；确保更新地图，使所有这些节点都指向合并图
• 如果两者都属于同一个子图，则它们必须在不同的颜色集中，否则图不是二分图

在您的情况下，每个边之后的子图映射可能如下所示：

1 2 -> {1: ({1}, {2}), 2: (see 1)}
2 3 -> {1: ({1, 3}, {2}), 2: (see 1), 3: (see 1)}
5 6 -> {1: ({1, 3}, {2}), 2: (see 1), 3: (see 1), 5: ({5}, {6}), 6: (see 5)}
1 5 -> {1: ({1, 3, 6}, {2, 5}), 2: (see 1), 3: (see 1), 5: (see 1), 6: (see 1)}