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&¤t->intLeft!=0)
{
intTravelled1=BFS(current->left,intTravelled+current->intLeft,visit);
current->left->visited=0;
leftvisit=1;
}
if(current->right->visited==0&¤t->intRight!=0)
{
intTravelled2=BFS(current->right,intTravelled+current->intRight,visit);
current->right->visited=0;
rightvisit=1;
}
if(current->up->visited==0&¤t->intUp!=0)
{
intTravelled3=BFS(current->up,intTravelled+current->intUp,visit);
current->up->visited=0;
upvisit=1;
}
if(current->down->visited==0&¤t->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();
}
