implementing Deapth First Search (non recursively)

[mum.roy.77]

edges.txt is used.it is the input adjacency list.
1 3
1 5
2 3
2 6
4 5
5 6

include<stdio.h>

include<stdlib.h>

include<conio.h>

int **adjL;
int v,*arr;
void dfs(int **adjL)




{


 int j,i=0,temp,dfslabel=1,s=0,k=0,top=0;
 int stack[v];
 int *flag;
 flag=(int*)calloc(v+1,sizeof(int));
 for(i=0;i<=v;i++)
 flag[i]=0;
 stack[++top]=1;
 flag[1]=3;
 stack[top]=1;
 while(1)
 {
        if(i==arr[stack[top]-1])
        {
             printf("examination of %d is complete",stack[top]);
             top--;
        }
        if(top==-1)
        break; 
        if(flag[adjL[stack[top]-1][i]]==0)
        {
              temp=adjL[stack[top]-1][i];
              stack[top++]=temp;
              i=0;
              flag[temp]=stack[top-1];
              printf("\nDFS label:%d ,current node=%d,linkprocessed %d to %d (tree edge)",dfslabel,stack[top-1],stack[top-1],temp);
              dfslabel++;
        }
        else
        {
              if(flag[adjL[stack[top]-1][i]]==stack[top-1])
              printf("\nbackedge");
              else
              printf("\ncycle");
              i++;
        }
 }


}




int main()
{
    FILE *fp;
    int *index;
    v=-1;
    int num1,num2;
    int i=0,j;



fp=fopen("edges.txt","r");
while(fscanf(fp,"%d %d",&num1,&num2)!=EOF)
{
    if(num1>v)
        v=num1;
    if(num2>v)
        v=num2;
}




printf("%d",v);
adjL=(int **)calloc(sizeof(int *),v);
arr=(int *)calloc(sizeof(int),v);
printf("\nHighest edge found = %d",v);
rewind(fp);
while(fscanf(fp,"%d %d",&num1,&num2)!=EOF)
{
    arr[num1-1]++;
    arr[num2-1]++;
}
rewind(fp);
for(i=0;i<=v-1;i++)
{
    adjL[i]=(int *)calloc(sizeof(int),arr[i]);
}
index=(int *)calloc(v,sizeof(int));
while(fscanf(fp,"%d %d",&num1,&num2)!=EOF)
{
    adjL[num1-1][index[num1-1]]=num2;
    index[num1-1]++;
    adjL[num2-1][index[num2-1]]=num1;
    index[num2-1]++;
}
for(i=0;i<=v-1;i++)
{
    printf("\n%d degree%d: ",i+1,arr[i]);
    for(j=0;j<=arr[i]-1;j++)
    {
        printf(" %d ",adjL[i][j]);
    }
}
printf("\n");
fclose(fp);
dfs(adjL);
getch();
return 0;


}

[Moschops]

We need a question. What does your code do that you think it shouldn't do, or what do you want it to do that it doesn't do, or does it not compile, or something else?

[mum.roy.77]

it's being compiled..bt if u run it,running till the adjacency list..can anyone plz help me in finding d logical error in my prog..

[nitin1]

As your code is not much readable and also, too complex for this trivial algorithm. I will you suggest you few links and then try to read your code again as what i feel after reading your code is that you haven't understood the algorithm correctly.

1. Click Here
2. Click Here
3. Click Here

After these three links, you will be ready to write code for DFS. hope it helps! thanks. ;)