February 21st, 2010, 11:45 AM

Checking for bipartite graph
Hi guys,
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.
Code:
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;
else
colour[w] = 1;
bipart(w);
}
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.");
return bipartite;
}
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;
bipart(w);
}
}
return bipartite;
}
In the main function, if(bipart(i) == 0), then print The graph is a bipartite graph.
Can anyone guide me?
Do appreciate any input.
Thanks!
Drendal
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?
Originally Posted by Drendal
I generated a rather simple code but am not sure if it works.
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.
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 = Depthfirst 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.