二部图的划分邻接矩阵
假设我有一个图 G 及其邻接矩阵 A。我知道 G 是二部的。 如何将 G 中的顶点分成始终形成二部图的两个集合？ 谢谢！
Lets say I have a graph G with its adjacency matrix A. I know that G is bipartite.
How can I split the vertices in G into the two sets that always form a bipartite graph?
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
声明一个大小等于顶点数的数组
，最初将每个元素设置为 0。然后通过图表执行深度优先搜索，记录您所在的“级别编号”。从 1 开始，随着每条边的遍历，在 1 和 2 之间交替。对于到达的每个顶点，将当前级别分配给which的相应条目，并且（如果之前为 0）递归处理其子级。之后，which的所有元素都将是 1 或 2，which[i]指示i属于哪个集合顶点。直观上，您可以想象，DFS 中从父级到子级的每次遍历都会使您“下降”一个级别，而每次返回遍历都会使您“上升”一级。根据二分性质，偶数层上的所有顶点只能连接到奇数层上的顶点，反之亦然，因此将节点标记为“偶数”或“奇数”足以将它们划分为两个集合。
如果您的图表包含多个组件，那么您当然需要为每个组件提供一个单独的 DFS。
Declare an array
whichof size equal to the number of vertices, setting each element to 0 initially. Then perform a depth-first search through the graph, recording the "level number" that you are on as you go. This starts at 1, and alternates between 1 and 2 with each edge traversed. For every vertex reached, assign the current level to the corresponding entry ofwhich, and (if it was previously 0) recurse to process its children. Afterwards, all elements ofwhichwill be either 1 or 2, andwhich[i]indicates which set vertexibelongs to.Intuitively, you can imagine that each traversal from parent to child in the DFS takes you "down" a level, and each traversal back takes you back "up". By the bipartite property, all vertices on even levels can be connected only to vertices on odd levels and vice versa, so labelling nodes "even" or "odd" suffices to partition them into the two sets.
If your graph contains more than one component, you will of course need a separate DFS for each component.