Writing a program to check if a graph is bipartite

Question

I need to write a program that checks if a graph is bipartite.

I read Wikipedia articles on graph coloring and a two-way graph . These two articles offer bipartity testing methods, such as searching for BFS, but I cannot write a program that implements these methods.

Answer 1

Why can not you? Your question is preventing someone from writing a program for you, since you don’t even mention any particular language ...

The idea is to start by placing a random node in the FIFO queue (also here ). The color is blue. Then repeat this until the nodes remain in the queue: dequeue a element. Color its neighbors with a different color than the extracted element, and insert (enqueue) each neighbor into the FIFO queue. For example, if you remove (extract) an element (node), color red, color its neighboring blue. If you select a blue node, paint its neighbors red. If there are no coloring conflicts, the schedule is bipartite. If you finish coloring the node with two different colors, then this will not be bipartite.

Like @Moron, what I described will only work for linked charts. However, you can apply the same algorithm for each connected component to make it work for any graph.

Answer 2

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/breadthSearch.htm

Please read this webpage using the first width search to check when you visited the node, check the current or odd current loop.

A graph is bipartite if and only if it does not contain an odd cycle.

Answer 3

A detailed implementation is as follows (C ++ version):

struct NODE { int color; vector<int> neigh_list; }; bool checkAllNodesVisited(NODE *graph, int numNodes, int & index); bool checkBigraph(NODE * graph, int numNodes) { int start = 0; do { queue<int> Myqueue; Myqueue.push(start); graph[start].color = 0; while(!Myqueue.empty()) { int gid = Myqueue.front(); for(int i=0; i<graph[gid].neigh_list.size(); i++) { int neighid = graph[gid].neigh_list[i]; if(graph[neighid].color == -1) { graph[neighid].color = (graph[gid].color+1)%2; // assign to another group Myqueue.push(neighid); } else { if(graph[neighid].color == graph[gid].color) // touble pair in the same group return false; } } Myqueue.pop(); } } while (!checkAllNodesVisited(graph, numNodes, start)); // make sure all nodes visited // to be able to handle several separated graphs, IMPORTANT!!! return true; } bool checkAllNodesVisited(NODE *graph, int numNodes, int & index) { for (int i=0; i<numNodes; i++) { if (graph[i].color == -1) { index = i; return false; } } return true; }