Writing a program to check if a graph is bipartite
I need to write a program that check if a graph is bipartite.
I have read through wikipedia articles about graph coloring and bipartite graph. These two article suggest methods to test bipartiteness like BFS search, but I cannot write a program implementing these methods.
Answer
Why can't you? Your question makes it hard for someone to even write the program for you since you don't even mention a specific language...
The idea is to start by placing a random node into a FIFO queue (also here). Color it blue. Then repeat this while there are nodes still left in the queue: dequeue an element. Color its neighbors with a different color than the extracted element and insert (enqueue) each neighbour into the FIFO queue. For example, if you dequeue (extract) an element (node) colored red, color its neighbours blue. If you extract a blue node, color its neighbours red. If there are no coloring conflicts, the graph is bipartite. If you end up coloring a node with two different colors, than it's not bipartite.
Like @Moron said, what I described will only work for connected graphs. However, you can apply the same algorithm on each connected component to make it work for any graph.