我该如何分割一个二分图按颜色？ [英] How do I partition a bipartite graph by color?

问题描述

例如，假设我有一个图G =（V，E），其中

For instance, suppose I have a graph G = (V, E) where

V = {A，B，C，D}
E = {（A，B），（A，D），（C，D）}

V = {A, B, C, D}
E = {(A, B), (A,D), (C, D)}

此图是二分，因此可以被分裂成两个不相交的集合{A，C}和{B，D}。我的第一个猜测是，我可以简单地走在图形和分配交替颜色，每个顶点。这样的话，或者是更复杂/比这更简单？是否有任何已知的算法呢？

This graph is bipartite, and thus can be split into two disjoint sets {A, C} and {B, D}. My first guess is that I can simply walk the graph and assign alternating colors to each vertex. Is this the case, or is it more complicated/simpler than this? Are there any known algorithms for this?

推荐答案

您的第一个猜测是正确的 - 遍历图形和备用

Your first guess is correct - traverse the graph and alternate.

该算法应该很简单。我会保持节点的两个队列访问，每种颜色一个。流行节点离开队列交替，标志其颜色，将任何未访问过的相邻节点到队列为相反的颜色。终止时访问了节点的数目+两个队列的长度=图中的节点的数目。

The algorithm should be simple. I'd keep two queues of nodes to visit, one for each colour. Pop nodes off the queues alternately, mark its colour, and push any non-visited adjacent nodes into the queue for the opposite colour. Terminate when the number of visited nodes + the length of both queues = number of nodes in the graph.

这篇关于我该如何分割一个二分图按颜色？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！