DFS sur un graphe orienté

Je mettais en œuvre Depth First Search sur un graphe orienté. Ci-dessous le code que j'ai implémenté jusqu'à présent mais qui donne une erreur d'exécution. En scrutant les erreurs, j'ai trouvé le pas récursif qui causait tous les problèmes. J'ai testé séparément toutes les autres étapes et ils fonctionnent correctement mais dès que je mets les étapes récursives cela donne une erreur d'exécution. L'entrée a été donnée dans le format de liste d'adjacence. S'il vous plaît aider!DFS sur un graphe orienté

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

Source

2017-10-21 Akash Bhardwaj

Bienvenue dans Stack Overflow. Veuillez publier l'entrée la plus simple qui produit l'erreur, ou mieux encore le coder en dur (c'est-à-dire l'écrire dans le code). – Beta

En outre, veuillez spécifier quelle est l'erreur que vous obtenez. –

Quel est le problème avec cette instruction 'list = (int **) malloc (sizeof (int) * n);'? N'avez-vous pas voulu dire 'list = malloc (sizeof * list * n);'? Qu'est-ce que '* list' (indice, ce n'est pas" int "), c'est pourquoi il est recommandé d'obtenir le' sizeof * var' plutôt que 'sizeof (type)' - vous pourriez juste obtenir le 'type' faux. (bien sûr, si vous êtes sur x86 (ou sur un autre système où pointer et int ont la même taille), vous n'êtes correct que par accident Voir: [** Dois-je afficher le résultat de malloc? **] (http: // stackoverflow.com/q/605845/995714) –

Votre tampon cause de code envahirent à cette ligne suivante:

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

Peut-être, vous vouliez dire nums [i ++]?

Source

2017-10-21 02:34:48 ning

DFS sur un graphe orienté

Répondre

Questions connexes