-
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! :D
-
-
Welcome, Drendal.
I can't help you with graphs. I read your post describing bipartite graphs elsewhere, but it's pretty much greek to me.
Whenever you post code, be sure to highlight it, and click on the # icon in the advanced editor's window (next to the smilies pull down list). Without that, your code will be squished all to the left hand side, and read like crap.
Why don't you edit your post on your code and put in the code tags, and I'm sure some of the brighter bulbs who know about graphs, will be along.
Do you have a very simple case to test your code on? How will you know when it's working right?