### Thread: Checking for bipartite graph

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2010
Posts
2
Rep Power
0

#### 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
2. No Profile Picture
Contributing User
Devshed Loyal (3000 - 3499 posts)

Join Date
May 2004
Posts
3,417
Rep Power
890
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?
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2010
Posts
2
Rep Power
0
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..
4. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
San Francisco Bay
Posts
1,939
Rep Power
1317
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):
Code:
```[0  A]
[A' 0]```
(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.