Thread: Bipartite graph checking

Hi,

How do I create a depth-first search algorithm to check if a graph is bipartite?

Any help on this would be very much appreciated!

Regards,

Drendal

Edit:

While I am able to create a dfs algorithm for a normal graph, I'm stuck with the bipartite problem.

My algorithm:

void dfs(int v)
{
int w;
count = count + 1;
sequence[count] = v; /*If not visited, sign the vertex with the visited sequence*/
visit[v] = 1;

for(w=1; w<=V; w++) /*Do the dfs recursivly*/
{
if(a[v][w] == 1 && visit[w] == 0)
{
parent[w]= v;
dfs(w);
}
}
}

count is initialized as 0 as a global variable.

Any pointers would be great!