Thread: Breadth First Search Traversal

  1. #1
    Registered User
    Join Date
    Aug 2012
    Location
    Quezon City, Philippines, Philippines
    Posts
    8

    Breadth First Search Traversal

    I have declared my 5 nodes. My only problem is my Breadth First Search Code. I can't get it to work. Can someone please help me with this one?

    Code:
    #include <conio.h>
    #include <stdio.h>
    typedef struct graph
    {
        int visited,intUp,intDown,intRight,intLeft;
        graph *up,*down,*right,*left;
    }Graph;
    
    int BFS(Graph *current,int intTravelled,int visit)
    {
            int intTravelled1,intTravelled2,intTravelled3,intTravelled4,leftvisit=0,rightvisit=0,upvisit=0,downvisit=0;
            current->visited=1;
            printf("visit: %d intTravelled: %d\n",visit,intTravelled);
            while(visit!=5)
            {
            visit++;
            if(current->left->visited==0&&current->intLeft!=0)
            {
                intTravelled1=BFS(current->left,intTravelled+current->intLeft,visit);
                current->left->visited=0;
                leftvisit=1;
            }
            if(current->right->visited==0&&current->intRight!=0)
            {
                intTravelled2=BFS(current->right,intTravelled+current->intRight,visit);
                current->right->visited=0;
                rightvisit=1;
            }
            if(current->up->visited==0&&current->intUp!=0)
            {
                intTravelled3=BFS(current->up,intTravelled+current->intUp,visit);
                current->up->visited=0;
                upvisit=1;
            }
            if(current->down->visited==0&&current->intDown!=0)
            {
                intTravelled4=BFS(current->down,intTravelled+current->intDown,visit);
                current->down->visited=0;
                downvisit=1;
            }
            }
        if(intTravelled1<=intTravelled2&&intTravelled1<=intTravelled3&&intTravelled1<=intTravelled4&&leftvisit==1)
            return intTravelled1;
        else if(intTravelled2<=intTravelled3&&intTravelled2<=intTravelled4&&rightvisit==1)
            return intTravelled2;
        else if(intTravelled3<=intTravelled4&&upvisit==1)
            return intTravelled3;
        if(downvisit==1)
            return intTravelled4;
        return intTravelled;
    }
    
    Graph city[5];
    void main()
    {
        clrscr();
        //City1 Middle
        city[0].up=&city[1];
        city[0].intUp=1;
        city[0].left=&city[2];
        city[0].intLeft=2;
        city[0].down=&city[3];
        city[0].intDown=3;
        city[0].right=&city[4];
        city[0].intRight=4;
        city[0].visited=0;
        //City2 Top
        city[1].up=NULL;
        city[1].intUp=0;
        city[1].left=&city[2];
        city[1].intLeft=1;
        city[1].down=&city[0];
        city[1].intDown=1;
        city[1].right=&city[4];
        city[1].intRight=2;
        city[1].visited=0;
        //City3 Left
        city[2].up=&city[1];
        city[2].intUp=1;
        city[2].left=NULL;
        city[2].intLeft=0;
        city[2].down=&city[3];
        city[2].intDown=3;
        city[2].right=&city[0];
        city[2].intRight=2;
        city[2].visited=0;
        //City4 Down
        city[3].up=&city[0];
        city[3].intUp=3;
        city[3].left=&city[2];
        city[3].intLeft=3;
        city[3].down=NULL;
        city[3].intDown=0;
        city[3].right=&city[4];
        city[3].intRight=1;
        city[3].visited=0;
        //City5 Right
        city[4].up=&city[1];
        city[4].intUp=2;
        city[4].left=&city[0];
        city[4].intLeft=4;
        city[4].down=&city[3];
        city[4].intDown=1;
        city[4].right=NULL;
        city[4].intRight=0;
        city[4].visited=0;
        //End Of Declaration of Map
        Graph *current=&city[0]; //Starts at city1
        int intTravelled=0,visit=0;
        intTravelled=BFS(current,intTravelled,visit);
        printf("%d",intTravelled);
        getch();
    
    }

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Your approach simply wont work.
    Try the method of using a queue.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Aug 2012
    Location
    Quezon City, Philippines, Philippines
    Posts
    8
    Can you explain it to me more? I'm just a beginner with graphs.

  4. #4
    Dweeb dojha00's Avatar
    Join Date
    Feb 2012
    Location
    Global
    Posts
    23
    Use matrix(matrix representation of graphs) and queue(BFS), will be a better option..
    1st by using matrix and queue get the proper sequence of displaying the nodes and then display the value...
    Your code is really too long and complex..
    What is life??

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Breadth First Search in C#
    By Loosexll in forum C# Programming
    Replies: 1
    Last Post: 08-27-2012, 07:33 AM
  2. Breadth-first search
    By jordanguyoflove in forum C Programming
    Replies: 9
    Last Post: 03-31-2009, 08:01 AM
  3. Using Breadth First Search
    By neandrake in forum C++ Programming
    Replies: 4
    Last Post: 05-06-2005, 05:13 PM
  4. Help me about the Breadth-First-Search??
    By john_tran in forum General AI Programming
    Replies: 1
    Last Post: 04-12-2005, 04:25 AM
  5. Help me about the Breadth-First-Search??
    By john_tran in forum C++ Programming
    Replies: 1
    Last Post: 04-09-2005, 02:33 AM