C / C++ / MFC

4-Oct-09 20:51

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++;
}
}

}

DeepakMega4-Oct-09 21:26

4-Oct-09 21:26

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[^]

zeego4-Oct-09 22:30

4-Oct-09 22:30

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

Saurabh.Garg4-Oct-09 22:53

Saurabh.Garg

4-Oct-09 22:53

For loops be for(i=0 ; i<MAX ; ++i)

front++; should be outside the for loop.

-Saurabh

zeego4-Oct-09 23:07

4-Oct-09 23:07

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

DeepakMega4-Oct-09 23:32

4-Oct-09 23:32

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

zeego4-Oct-09 23:45

4-Oct-09 23:45

thanks for the reply. I am using the turbo c 3.0 IDE, I never knew it could run in visual studio. Sniff | :^)

I had a hard time debugging this inside the turbo c ide so I posted it here.
Mike.

zeego12-Oct-09 20:52

12-Oct-09 20:52

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

#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++;
			}


	   }

DeepakMega12-Oct-09 22:17

12-Oct-09 22:17

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

zeego12-Oct-09 23:14

12-Oct-09 23:14

Hello mate, thanks for the reply. I need breadth first traversal on a graph, but its not working properly. Unsure | :~

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. Sniff | :^)

Thanks and best regards, Mike.

DeepakMega12-Oct-09 22:48

12-Oct-09 22:48

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

zeego12-Oct-09 23:11

12-Oct-09 23:11

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 | :confused:

DeepakMega12-Oct-09 23:45

12-Oct-09 23:45

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++;
			}


	   }

zeego13-Oct-09 21:39

13-Oct-09 21:39

Thanks so much for the reply and the link, the program is working fine now. Big Grin | :-D

Best Regards, Mike.

zeego12-Oct-09 23:38