有向圖上的DFS

我在一個有向圖上實現了深度優先搜索。下面是我迄今爲止實現的代碼，但它給出了運行時錯誤。在仔細檢查錯誤時，我發現遞歸步驟造成了所有的麻煩。我已經單獨測試了所有其他步驟，並且它們的功能正常，但是一旦我將遞歸步驟給出了運行時錯誤，輸入就會以鄰接列表格式給出。請幫忙！有向圖上的DFS

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

來源

2017-10-21 Akash Bhardwaj

歡迎來到Stack Overflow。請發佈產生錯誤的最簡單的輸入，或者更好地對其進行硬編碼（即將其寫入代碼中）。 – Beta

另外，請說明您收到的錯誤是什麼。 –

這條語句有什麼問題'list =（int **）malloc（sizeof（int）* n）;'？你不是指'list = malloc（sizeof * list * n）;'？什麼是'* list'（提示，它不是'int'），這就是爲什麼建議使用'sizeof * var'而不是'sizeof（type）' - 你可能會得到'type'錯誤。（當然，如果你在x86上（或者其他指針和int大小相同的系統），你只是偶然發現了錯誤，請參考：[**我是否使用了malloc？**結果（http：// stackoverflow.com/q/605845/995714） –

您的代碼導致緩衝區佔領這個下面一行：

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

也許，你的意思是NUMS [我++]？

來源

2017-10-21 02:34:48 ning

有向圖上的DFS

回答

相關問題