How do I partition a bipartite graph by color?

问题:

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

V = {A, B, C, D}
E = {(A, B), (A,D), (C, 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?

回答1:

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.

回答2:

Traverse the graph and alternate, if it doesn't succeded it means that your graph is not bipartite.

回答3:

If you are sure that the graph is biparte, then you can just assign colors alternating them for traversing each vertex, as it holds that:

A graph is bipartite if and only if it is 2-colorable.

回答4:

From Wikipedia (http://en.wikipedia.org/wiki/Bipartite_graph)

If a bipartite graph is connected, its bipartition can be defined by the parity of the distances from any arbitrarily chosen vertex v: one subset consists of the vertices at even distance to v and the other subset consists of the vertices at odd distance to v.

Thus, one may efficiently test whether a graph is bipartite by using this parity technique to assign vertices to the two subsets U and V, separately within each connected component of the graph, and then examine each edge to verify that it has endpoints assigned to different subsets.

回答5:

I implemented it in my graph drawing tool, you can see my code in JavaScript.

I just marked first vertex as left partity, then recursively marked it's neighbours as right partity, recursively mark their neighbours as left partity... If you find correctly marked node, stop recursion of this branch. If you find uncorrectly marked node, graph is not bipartite.

Maybe it can be done simpler, but during last few months I had some hard Prolog - Haskell coding days, maybe it had affected my brain and now I see recursion in everything :-D

回答6:

Just in case anyone's curious, here's the code I came up with:

def dfs(root, colorings):
    to_visit1 = deque()
    to_visit2 = deque()
    to_visit1.append(root)
    while len(to_visit1) != 0 or len(to_visit2) != 0:
        dfs_color(to_visit1, to_visit2, True, colorings)
        dfs_color(to_visit2, to_visit1, False, colorings)

def dfs_color(queue, opposite_queue, color, colorings):
    while len(queue) != 0:
    v = queue.pop()
    if v in adjacency_list:
        colorings[v] = color
        neighbors = adjacency_list[v]
        del adjacency_list[v]
        for neighbor in neighbors:
        opposite_queue.append(neighbor)

Admittedly, this isn't my best code. I'm using True/False as the color because when I used recursion, it made it easy to just say not color. Of course, I had to change it because I blew my stack on bigger graphs. Also to give credit where due, this code is based on the wikipedia code for DFS.

Although as has been pointed out, I think this may just be a disguised BFS.