algorithm - 将图转换为二分图

Question

正在看BFS算法的应用。我阅读的应用程序之一是检查给定图是否为二分图。现在我想知道，是否有任何算法可以将图转换为二分图。

例如我们给出一组边作为

E={ (4, 1),( 1 ,2), (2 ,3),( 7, 2),( 1 ,5),( 8 ,4), (5 ,8),( 8, 9)}

和顶点集

V= { 1,2,3,4,5,6,7,8}

我们必须创建二分集/图。

预期输出为:-

s1={1 ,4, 8, 1 ,7 ,3}
s2={2, 5, 6, 9}

Answer 1

检查图是否为二分图的一般 BFS 算法是:

1. 从顶点 v_0 开始，并将其标记为 s1。
2. 将 v_0 的所有邻居标记为 s2，并将它们排队。
3. 将邻居的所有邻居标记为s1，并排队

如果在任何时候，您将一个已标记为 s1 的顶点标记为 s2，反之亦然，则该图不是二分图。相反，如果您最终得到一个空队列，那么您就完成了，并且您拥有了您的分区。

编辑

如果您想知道的是如何从一般图构建二部图，您应该首先添加一个度量来比较两个不同的解决方案:否则，删除所有边并将顶点随机分配给两个组，将始终从任何给定的一个生成一个(平凡的)二分图。