Wrong Output, Cant catch the mistake (DFS)

zeego

Hi I made the following program for depth first search but I am having wrong path. Can anyone catch or tell me what I am doing wrong here. I dont know much how to use the debugger in turbo c professional. Thanks and regards, Mike. #include <stdio.h> #include <conio.h> #define MAX 6 // Node/Vertex count int adj[MAX][MAX]={ // Adjacency Matrix 2x2 {0,1,1,1,0,0}, {1,0,0,0,1,1}, {1,0,0,0,0,0}, {1,0,0,0,0,0}, {0,1,0,0,0,0}, {0,1,1,0,0,0} }; int visited[MAX]; // Visited array void bfs(int goal); // bfs function int main () { int g=5; //set Goal node clrscr(); printf("The nodes order is "); bfs(g); return 0; } void bfs(int goal) { int queue[MAX]; int i,front,rear,root; front=rear=0; for (i=1;i<=MAX;i++) visited[i]=0; visited[goal]=1; queue[rear++]=goal; while(front!=rear) { root=queue[front]; for(i=1;i<=MAX;i++) { if (adj[root][i] && !visited[i]) { visited[i]=1; queue[rear++]=i; printf("%d",i); } front++; } } }

DeepakMega

Is the queue circular , if so you need to check for ends and rotate the queue's front/rear back to 0. Refer here Circular Queue[^]

zeego

No, it is not circular. It is just a FIFO queue.

Saurabh Garg

For loops be for(i=0 ; i `front++;` should be outside the for loop. -Saurabh

zeego

Output is wrong if I take it out of the for loop :((

DeepakMega

Sry im not good at algorithms, when i ran your code in vs there was an error in the 3rd line of the code below

root=queue[front];
for(i=1;i<=MAX;i++)
{
if (adj[root][i] && !visited[i])

ie : adj[root][i] , the root value was garbage, and root=queue[front]; here front was 6 and queue[6] was uninitialized

zeego

thanks for the reply. I am using the turbo c 3.0 IDE, I never knew it could run in visual studio. :^) I had a hard time debugging this inside the turbo c ide so I posted it here. Mike.

zeego

Cant get it to work. The output is a blank screen :(

#include <stdio.h>
#include <conio.h>
#define MAX 6 // Node/Vertex count
int adj[MAX][MAX]={ // Adjacency Matrix 2x2
{0,1,1,1,0,0},
{1,0,0,0,1,1},
{1,0,0,0,0,0},
{1,0,0,0,0,0},
{0,1,0,0,0,0},
{0,1,1,0,0,0}
};

int visited[MAX]; // Visited array
void bfs(int goal); // bfs function

int main ()
{
int s=3; //set Source node
clrscr();
printf("The nodes order is ");
bfs(s);
return 0;

void bfs(int source)
{
int queue[MAX];
int i,front,rear,root;
front=rear=0;

   for (i=1;i<MAX;i++)
   {
	   visited\[i\]=0;
   }



   queue\[++rear\]=source;
   visited\[source\]=1;

   printf("%d :",source);

	while(rear!=front)
		{
			root=queue\[++front\];
			for(i=0;i<MAX;i++)

				if (adj\[root\]\[i\] && !visited\[i\])
				{
					queue\[rear++\]=i;
					visited\[i\]=1;
					printf("%d",i);
				}


			front++;
		}


   }

DeepakMega

What is your required output. Please specify the output needed for the above program inputs.

DeepakMega

Changes made : for (i=0;i<MAX;i++) { visited[i]=0; } queue[rear++]=source; // its not ++rear as it becomes queue[1] instead of queue[0] ..... ..... while(rear!=front) { root=queue[front]; //no need to increment front here This is the output i got The nodes order is 3 :01245

zeego

The program is for breadth first traversal of a graph. The output is there but program is crashing. I have to use break to stop from infinite looping.:confused:

zeego

Hello mate, thanks for the reply. I need breadth first traversal on a graph, but its not working properly.:~ The program hangs inside my turbo c ide and I have to use 'break' to get out of the infinite loop. Also I dont know how to debug inside turbo c 3 IDE so having a hard time debugging the problem in my code.Please help me. :^) Thanks and best regards, Mike.

zeego

Thanks for the reply mate. Isn't ++rear=rear+1 ? What is the difference between the two ? Also queue[rear++]=source means queue[0]=source ? Best regards, Mike.

DeepakMega

rear=0; 1) queue[rear++]=source; // is same as queue[0]=source; and rear increments after assignment; 2) queue[++rear]=source; // is same as queue[1]=source; here rear increments before assignment; Its from the precedence of operators in c, check operator precedence table[^] The below program with minor changes as specified above runs fine in my turbo c , just add a getch() in main

#include <stdio.h>
#include <conio.h>
#define MAX 6 // Node/Vertex count
int adj[MAX][MAX]={ // Adjacency Matrix 2x2
{0,1,1,1,0,0},
{1,0,0,0,1,1},
{1,0,0,0,0,0},
{1,0,0,0,0,0},
{0,1,0,0,0,0},
{0,1,1,0,0,0}
};

int visited[MAX]; // Visited array
void bfs(int goal); // bfs function

int main ()
{
int s=3; //set Source node
clrscr();
printf("The nodes order is ");
bfs(s);
getch();
return 0;

void bfs(int source)
{
int queue[MAX];
int i,front,rear,root;
front=rear=0;

   for (i=0;i<MAX;i++)
   {
	   visited\[i\]=0;
   }



   queue\[rear++\]=source;
   visited\[source\]=1;

   printf("%d :",source);

	while(rear!=front)
		{
			root=queue\[front\];
			for(i=0;i<MAX;i++)

				if (adj\[root\]\[i\] && !visited\[i\])
				{
					queue\[rear++\]=i;
					visited\[i\]=1;
					printf("%d",i);
				}


			front++;
		}


   }

zeego

Thanks so much for the reply and the link, the program is working fine now. :-D Best Regards, Mike.