Click here to Skip to main content
15,943,008 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Hai...i wrote a program to perform depth first search.The code is given below.But inside the DFS_VISIT() function the discovery time is printing correctly.But from the main function it is printing as 0 for all nodes.
C++
    v[u]->discovery=++time;
printf("\nDiscovery of %d:%d",u,v[u]->discovery);


i can print v[u]->discovery from the DFS_visit() as above.bt the same dosnt print from main function.*v[] is declared as global.all other elements which is accessible via *v[] is printing correctly from main.

I am not gettg y this happening.Sombody please help me.Full code is given below.

C++
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<graphics.h>
#include<string.h>
struct node
{
	int item;
	char color[5];
	int discovery,finishing,parent;
	struct node *next;
};
struct graph
{
 int x,y;
}graph[10];
struct node *nwptr=NULL,*v[10],*temp=NULL;
int time=0,n;
void DFS();
void DFS_VISIT(int);
int main()
{
	int a,i,j,temp1,temp2,x,y,k;
	char string[10];
	int gdriver=DETECT,gmode;
	clrscr();
	printf("\nEnter the no. vertex :");
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
	    v[i]=(struct node*)malloc(sizeof(struct node));
	    printf("\nEnter the value of vertex   :");
	    scanf("%d",&v[i]->item);
	    v[i]->next=NULL;
	    printf("\nEnter the no. of adj vertex :");
	    scanf("%d",&a);
	    for(j=1;j<=a;j++)
	    {
	       nwptr=(struct node*)malloc(sizeof(struct node));
	       printf("\nEnter the value of adj vertex :");
	       scanf("%d",&nwptr->item);
	       nwptr->next=NULL;
	       for(temp=v[i];temp->next!=NULL;temp=temp->next);
		 temp->next=nwptr;
	    }
	}
	printf("\n      ADJACENCY LIST\n");
	for(i=1;i<=n;i++)
	{
	    printf("\n%d",v[i]->item);
	    for(temp=v[i]->next;temp!=NULL;temp=temp->next)
	      printf("->%d",temp->item);
	}
	printf("\nPress any key to continue...\n");
	getch();
	initgraph(&gdriver,&gmode,"E:\\ProGRAMZ\\TC\\BGI");
	temp1=n/2;
	temp2=n-temp1;
	setfillstyle(SOLID_FILL,WHITE);
	k=50;
	for(i=1;i<=temp1;i++)
	{
	    fillellipse(k,50,10,10);
	    graph[i].x=k;
	    graph[i].y=50;
	    k+=50;
	}
	k=50;
	for(j=1;j<=temp2;j++,i++)
	{
	    fillellipse(k,100,10,10);
	    graph[i].x=k;
	    graph[i].y=100;
	    k+=50;
	}
	for(i=1;i<=n;i++)
	{

	    for(temp=v[i]->next;temp!=NULL;temp=temp->next)
	       line(graph[i].x,graph[i].y,graph[temp->item].x,graph[temp->item].y);
	    itoa(v[i]->item,string,10);
	    setcolor(0);
	    outtextxy(graph[i].x-3,graph[i].y-3,string);
	    setcolor(15);
	}
	getch();
	DFS();
	outtextxy(10,700,"\nPress any key to continue...\n");
	getch();
	cleardevice();
	printf("\nNODE\tDISCOVERY\tFINISHING\tPARENT\tCOLOR\n");
	for(i=1;i<=n;i++)
	printf("\n%d\t%d\t\t%d\t\t%d\t%s",v[i]->item,v[i]->discovery,v[i]->finishing,v[i]->parent,v[i]->color);
	getch();
	return(0);
}
void DFS()
{
	int i;
	for(i=1;i<=n;i++)
	{
	  strcpy(v[i]->color,"WHITE");
	  v[i]->discovery=NULL;
	  v[i]->finishing=NULL;
	  v[i]->parent=NULL;
	}
	time=0;
	for(i=1;i<=n;i++)
	{
	  if(strcmp(v[i]->color,"WHITE")==0)
	     DFS_VISIT(v[i]->item);
	}
}
void DFS_VISIT(int u)
{
	strcpy(v[u]->color,"GRAY");
	v[u]->discovery=++time;
	printf("\nDiscovery of %d:%d",u,v[u]->discovery);
	for(temp=v[u]->next;temp!=NULL;temp=temp->next)
	{
	   if(strcmp(v[temp->item]->color,"WHITE")==0)
	   {
	      v[temp->item]->parent=u;
	      DFS_VISIT(temp->item);
	   }
	}
	strcpy(v[u]->color,"BLACK");
	v[u]->finishing=++time;
}
Posted
Updated 19-Feb-12 23:33pm
v3

1 solution

This is certainly not easy to figure out, your use of offest values into the array of nodes seems overly complex, and probably fraught with danger. You are also using static variables within your functions rather than passing them as parameters, again a bad idea.

The only thing I could see was that you call function DFS() in main() before printing node data, but DFS() appears to delete the node data.
 
Share this answer
 
Comments
nithya.nampoothiri 20-Feb-12 5:06am    
Fist we are finding the adjacency list in main().Then we r drawing a graph with the adjacency list.After that we r calling DFS.Inside DFS we r finding all valuses.After the completion of DFS just printing the node color,discovery time n all.But all other data is printing correctly except the discovery time.To know whether the discovery time is finding correctly i gav a printf stmt inside DFS_VISIT().The data printing correctly inside DFS_VISIT.But the same data is not printing frm main function.(Here nothing is given to delete the node data).
Richard MacCutchan 20-Feb-12 5:14am    
As I said above, your code is very complicated, in fact almost impossible to understand. I can only suggest you spend some more time with your debugger to see when and where these values get set/unset.
nithya.nampoothiri 20-Feb-12 5:39am    
i tried all d way. am nt troubling wid any of its concepts..i just wondering y a variable which is in gloabal scope n which is assigning new values correctly inside a funcion showing as 0 in main function.Anyway thanx 4 ur reply...am waitg whethr sombody cn figure it out or not.
Richard MacCutchan 20-Feb-12 5:53am    
all d way ... wondering y ... 4 ur reply
Please do not use txtspk, it makes you appear childish and not as a professional developer.

As I said before, your code is almost impossible to understand, owing to your use of global variables, meaningless variable names and fixed indices rather than pointers. you can either spend some time with your debugger or add a lot more printf() statements to try and find out what is happening. But sooner or later you need to revisit your program design and come up with something cleaner and more logical.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900