February 21st, 2010, 11:45 AM
Checking for bipartite graph
Well I have an assignment which requires me to check if a graph is bipartite or not using a dfs algorithm. I generated a rather simple code but am not sure if it works.
In the main function, if(bipart(i) == 0), then print The graph is a bipartite graph.
int bipart(int v)
int w, bipartite=0;/* colour = 0 (not visited), =1 (blue), = 2 (red) */
count = count + 1;
sequence[count] = v;
visit[v] = 1;
if(colour[v] == 0) /* Starting vertex would have not been visited */
colour[v] = 1;
for(w=1; w<=V; w++)
if(a[v][w] == 1 && visit[w] == 0 && colour[w] == 0) /* Adjacent vertex which has not been visited and coloured */
parent[w] = v;
if(colour[v] == 1)
colour[w] = 2;
colour[w] = 1;
else if(a[v][w] == 1 && visit[w] == 1 && colour[w] == colour[v]) /*Adjacent vertex visited and of similar colour as parent*/
bipartite = bipartite + 1;
printf("\nThe graph is not a bipartite graph.");
else if(a[v][w] == 1 && visit[w] == 1 && colour [w] != colour[v]) /*Adjacent vertex visited and of different colour as parent*/
parent[w] = v;
Can anyone guide me?
Do appreciate any input.
February 21st, 2010, 12:14 PM
Interesting problem. What does DFS stand for? Is this some variation on the parity scheme?
It seems you have not posted enough of your code. Where are colour and visit defined?
Well test it and find out. Feed it graphs that are known to be bipartite and not bipartite. Use sets of graphs that are 1, 2, 3, odd, even length number of nodes in both categories. Make sure you have bipartite graphs with only 1 node in one of the sets and try building those sets with the node at the start, middle and end of the graph.
Originally Posted by Drendal
Why don't these schools teach unit testing before they jump into algorithms?
I no longer wish to be associated with this site.
February 21st, 2010, 02:06 PM
DFS = Depth-first search
Oh and I think i forgot to mention that it's coded in C.
I would test it out if I knew how to represent a bipartite graph in adjacency matrix form but I'm totally clueless on it. I just built this code solely based on theory so I'm not sure if it works.. :(
visit[v] is basically an array which will note the vertices of the graph which have been traversed by the dfs algorithm.
and colour[v] is also an array initialized in the start of the main function, basically since a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets, colour[v] = 1 is one set whereas colour[v] = 2 is another set.
Not too sure if my logic is right here..
February 22nd, 2010, 11:01 PM
I'm assuming we're dealing with undirected graphs? (There's a similar characterization for directed graphs.) An easy way to generate bipartite adjacency matrices is (in block form): (where A' is the transpose of A). In fact, if M is the adjacency matrix of an arbitrary graph, then the graph is bipartite if and only if PMP' is of the above form for some permutation matrix P.