Thread: Bipartite graph checking

  1. #1
    Registered User
    Join Date
    Feb 2010

    Bipartite graph checking


    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!




    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;

    count is initialized as 0 as a global variable.

    Any pointers would be great!
    Last edited by Drendal; 02-21-2010 at 08:54 AM.

  2. #2
    Registered User
    Join Date
    Feb 2010
    Hmmmm anyone?

  3. #3
    Registered User
    Join Date
    Sep 2006
    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?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Buidl Library with ./configure script
    By Jardon in forum C Programming
    Replies: 6
    Last Post: 07-24-2009, 09:36 AM
  2. Profiler Valgrind
    By afflictedd2 in forum C++ Programming
    Replies: 4
    Last Post: 07-18-2008, 09:38 AM
  3. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  4. error help making no sense
    By tunerfreak in forum C++ Programming
    Replies: 5
    Last Post: 04-17-2007, 07:55 PM
  5. Problems about gcc installation
    By kevin_cat in forum Linux Programming
    Replies: 4
    Last Post: 08-09-2005, 09:05 AM