我正在阅读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}
最佳答案
检查图是否为二部图的一般bfs算法是：
从顶点v_0开始，并将其标记为s1。
将所有v_0的邻居标记为s2，并对其进行排队。
将邻居的所有邻居标记为s1，并将其排队
如果在任何一点上，将一个已经标记为s1的顶点标记为s2，或者反之亦然，则该图不是二分图。相反，如果最后出现一个空队列，那么就完成了，并且有了分区。
编辑
如果您想知道的是如何从一个一般的二分图构建一个二分图，那么您应该首先添加一个度量来比较两个不同的解决方案：否则，删除所有边并将顶点随机分配给两个组，将始终从任何给定的一个二分图生成（平凡的）二分图。
关于algorithm - 将图转换为二部图，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/18504895/