Wrong Output, Cant catch the mistake (DFS)

[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.