DFS on a directed graph

Question

I was implementing Depth First Search on a directed graph.Below is the code I have implemented so far but it gives runtime error. On scrutinising the errors I found the recursive step causing all the trouble. I have separately tested all the other steps and they function properly but as soon as I put the recursive steps it gives runtime error.The input has been given in adjacency list format. Please help!

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

struct vertex{
    int d,f;
    int color;
    int length;
    int mark;
    int* adj_list;
};

int time=0;

void DFS(struct vertex* v,struct vertex node,int n,int time){
    v[node.mark].d=++time;
    v[node.mark].color=1;
    int itr=v[node.mark].length;
     for(int i=0;i<itr;i++){
        int curr=node.adj_list[i];
        if(v[curr].color==0){
            DFS(v,v[curr],n,time);
        }
    }
    v[node.mark].f=++time;
    v[node.mark].color=2;
    printf("%d",node.mark);
    return;
}

 int main(void) {int n,num,i=0,j=0;
    scanf("%d",&n);
    int** list;
    struct vertex* v;
    v=(struct vertex*)malloc(sizeof(struct vertex)*n);

    list=(int**)malloc(sizeof(int)*n);
    int* nums;
    nums=(int*)malloc(sizeof(int)*n);
    for(i=0;i<n;i++){
        nums[i]=0;
    }
    i=0;
    do{
        scanf("%d",&num);
        if(num!=-1){
            nums[j++]=num;
        }
        else if(num==-1){
            v[i].length=j;
            list[i]=(int*)malloc(sizeof(int)*j);
            for(int k=0;k<j;k++){
                list[i][k]=nums[k];
                nums[k]=0;
            }
            i++;
            j=0;
        }
    }while(i<n);

    for(i=0;i<n;i++){
        v[i].d=INT_MAX;
        v[i].f=INT_MAX;
        v[i].color=0;
        v[i].mark=i;
        v[i].adj_list=list[i];
    }

    for(i=0;i<n;i++){
        printf("%d ",v[i].mark);
    }

    DFS(v,v[0],n,time);

    return 0;
}

Welcome to Stack Overflow. Please post the simplest input that produces the error, or better still hard-code it (i.e. write it into the code). — Beta, Oct 21 '17 at 02:03
What's wrong with this statement `list=(int**)malloc(sizeof(int)*n);`? Didn't you mean `list = malloc (sizeof *list * n);`? What is `*list` (hint, it's not `'int'`), that is why it is recommended to get the `sizeof *var` rather that `sizeof (type)` -- you just might get the `type` wrong. (of course if you are on x86 (or other system where pointer and int are the same size), you are only correct by accident. See: [**Do I cast the result of malloc?**](http://stackoverflow.com/q/605845/995714) — David C. Rankin, Oct 21 '17 at 04:46

score 0 · Answer 1 · answered Oct 21 '17 at 02:34

0

Your code cause buffer overran at this following line:

do {
  ...
  nums[j++]=num; 
  ...
} while (i < n);

Perhaps, you meant nums[i++]?

answered Oct 21 '17 at 02:34

stensal

401
4
8

DFS on a directed graph

1 Answers1