Member Avatar for 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;


}
  • 3 Contributors
  • 3 Replies
  • 225 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by nitin1

Dani AI

Generated

A short, practical diagnosis and a clean iterative pattern to follow.

The symptoms you describe () and the code show three common problems: (1) allocation/initialization mistakes (wrong order/arguments to calloc, arrays not zeroed, using v before proper allocation), (2) a single global i used to walk neighbours instead of a per-node iterator, and (3) stack push/pop and parent-check logic that causes incorrect “cycle/backedge” reporting or infinite loops. rightly asked what the actual problem is; ’s reading suggestions are useful for theory, but the bug is in the implementation details below.

Checklist to fix first

  • Read edges once to compute v, then allocate arrays sized v+1 (use 1-based nodes or convert to 0-based consistently).
  • Use calloc(count, sizeof(type)) (count first) and check returned pointers.
  • Zero the degree array before counting edges.
  • Build adjacency lists using an index[] that starts at 0 and increments.
  • In DFS, do NOT use a single i. Keep a next[] per node (next neighbour index) or push pairs (node, nextIndex) on the stack.
  • For undirected graphs, ignore the immediate parent when testing for back edges.
  • Avoid conio.h/getch() for portability; use portable I/O and test with small graphs first.

Minimal iterative DFS pattern (conceptual C code)

/* nodes 1..v, adj[u] is int* of length deg[u] */
void dfs_iter(int v, int **adj, int *deg, int start) {
    int *stack = malloc((v+1)*sizeof(int));
    int *next = calloc(v+1, sizeof(int)); /* per-node iterator */
    int *state = calloc(v+1, sizeof(int)); /* 0 white,1 gray,2 black */
    int top = 0;
    stack[++top] = start; state[start] = 1;
    while (top > 0) {
        int u = stack[top];
        int parent = (top >= 2 ? stack[top-1] : 0);
        if (next[u] < deg[u]) {
            int w = adj[u][ next[u]++ ];
            if (state[w] == 0) { state[w] = 1; stack[++top] = w; } 
            else if (state[w] == 1 && w != parent) { /* back edge */ }
        } else { state[u] = 2; top--; /* finished u */ }
    }
    free(stack); free(next); free(state);
}

Quick debugging tips

  • Print deg[] and each adj[u] immediately after building them.
  • Run under AddressSanitizer/Valgrind for out-of-bounds or use-after-free.
  • Test on tiny graphs (2–6 nodes) to validate push/pop and parent checks.

Applying those fixes will stop the loop after the adjacency print and produce correct DFS labels and finished events.

Recommended Answers

All 3 Replies

Member Avatar for 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?

Member Avatar for 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..

Member Avatar for 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. ;)

Edited by nitin1
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.