graph - 二部图的划分邻接矩阵

Question

假设我有一个图 G 及其邻接矩阵 A。我知道 G 是二分的。如何将 G 中的顶点拆分为始终形成二分图的两组？谢谢！

Answer 1

声明一个which大小等于顶点数的数组，最初将每个元素设置为 0。然后在图形中执行深度优先搜索，边走边记录你所在的“级别编号”。这从 1 开始，并在遍历每条边时在 1 和 2 之间交替。对于到达的每个顶点，将当前级别分配给 的相应条目which，并且（如果之前为 0）递归处理其子级。之后， 的所有元素which将是 1 或 2，并which[i]指示集合顶点i属于哪个集合。

直观地，您可以想象在 DFS 中从父级到子级的每次遍历都会使您“下降”一个级别，而每次回溯都会使您“向上”返回。通过二分属性，偶数层上的所有顶点只能连接到奇数层上的顶点，反之亦然，因此将节点标记为“偶数”或“奇数”就足以将它们分成两组。

如果您的图表包含多个组件，那么您当然需要为每个组件提供单独的 DFS。