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

Question

给定图中边的多个输入，例如(第一行是连接数):

4
1 2
2 3
5 6
1 5

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

Answer 1

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

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

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

相反，为每个(仍然)断开连接的子图跟踪两组具有颜色 A 和颜色 B 的节点。所以当你添加一条边 (x, y) 时:

• 检查子图 x 和 y 属于(使用某种 map /字典)
• 如果都不属于子图，则开始一个新的子图
• 如果一个属于子图，但另一个不在图中，则给另一个节点与已包含节点相反的颜色
• 如果都属于不同的子图，则将子图合并为一个(合并颜色集)；这可能需要翻转其中一个图形的颜色，以便 x 和 y 不会以相同的颜色结束；确保更新 map ，以便所有这些节点都指向合并后的图
• 如果两者属于同一个子图，则它们必须在不同的颜色集中，否则该图不是二分图

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

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)}