DFS (parcours en profondeur) adaptation

[alakaabar]

Bonsoir ,

j´ai un peu de mal a adapter un algorithme censé faire un Depth first search avec des entree/sorties comme suit :



et voici le code utilisé:

#include<stdio.h>
  
typedef struct node
{
    struct node *next;
    int vertex;
}node;
  
node *G[20];  
//heads of linked list
int visited[20];
int n;
void read_graph();
//create adjacency list
void insert(int,int); 
//insert an edge (vi,vj) in te adjacency list
void DFS(int);
  
void main()
{
    int i;
    read_graph();
    //initialised visited to 0
    
    for(i=0;i<n;i++)
        visited[i]=0;
  
    DFS(0);
}
  
void DFS(int i)
{
    node *p;
    
    printf("\n%d",i);
    p=G[i];
    visited[i]=1;
    while(p!=NULL)
    {
       i=p->vertex;
        
       if(!visited[i])
            DFS(i);
        p=p->next;
    }
}
  
void read_graph()
{
    int i,vi,vj,no_of_edges;
    printf("Enter number of vertices:");
    
    scanf("%d",&n);
  
    //initialise G[] with a null
    
    for(i=0;i<n;i++)
    {
        G[i]=NULL;
        //read edges and insert them in G[]
        
        printf("Enter number of edges:");
           scanf("%d",&no_of_edges);
  
           for(i=0;i<no_of_edges;i++)
        {
            printf("Enter an edge(u,v):");
            scanf("%d%d",&vi,&vj);
            insert(vi,vj);
        }
    }
}
  
void insert(int vi,int vj)
{
    node *p,*q;
     
    //acquire memory for the new node
    q=(node*)malloc(sizeof(node));
    q->vertex=vj;
    q->next=NULL;
  
    //insert the node in the linked list number vi
    if(G[vi]==NULL)
        G[vi]=q;
    else
    {
        //go to end of the linked list
        p=G[vi];
        
        while(p->next!=NULL)
            p=p->next;
        p->next=q;
    }
}

mais le probleme c´est que j´ai aucune idee de comment le changer pour qu´il soit bien conforme au tableau d´en haut .. quelqu´un peut me donner un conseil ou une petite idee svp ?



Merci !
-----

[imoca]

Bonjour,

La fonction read_graph() a 2 boucles en la variables i.

[alakaabar]

y´a un truc que je capte pas dans ce code , si je lui donne cet input :


Normalement quand on arrive au 7 , y´a la condition de while n´est plus valable et donc on sert de cet boucle la mais apres je ne sais pas ca marche le backtracking pour afficher les autres valeurs de la liste d´adjacence

[imoca]

Le résultat est bon, après avoir atteins le sommet 7, la fonction dfs(7) s'arrête et retourne a dfs(5) qui s'arrete ...dfs(0) poursuit avec 2...

[A voir en vidéo sur Futura]

[alakaabar]

Bin je comprend pas comment ca retourne a dfs(5) vu que y´a aucune instruction apres la boucle while .... sinon y´a un autre probleme c´est que si je commence par 1 en tant que premier vi , on a le G[0]->vertex == NULL ce qui fait que la boucle while s´arrete tout de suite et n´affiche que 0

[imoca]

Logique, si tu demande le parcours en profondeur depuis le sommet 0 et que ton graphe commence à 1.

[alakaabar]

Est ce que tu aurais une idee de comment adapter ce code la avec les inputs du tableau en haut ? parce que je bloque des que je pense a l implementer en liste d´ádjacence