Traçage du graphe BFS en utilisant une file d'attente [C]

Question

J'étudie des graphes pour l'instant, et j'utilise C. Quand je représente un graphe avec une liste d'adjacence, j'ai besoin d'une file d'attente pour une traversée BFS. Cependant, j'ai quelques problèmes avec le code - je ne suis pas sûr si j'ai bien compris le concept d'une traversée bfs avec des files d'attente.

J'ai collé le code commenté ci-dessous, j'espère que c'est lisible. Quelqu'un peut-il vérifier, ou au moins fournir des informations sur la façon de tirer le bon chemin?

typedef struct { 
    char name[21], surname[21]; 
    double gpa; 
} STUDENT; 

typedef struct { 
    int index; 
    struct graph *next; 
    STUDENT s; 
} GRAPH_NODE; 

typedef struct { 
    GRAPH_NODE *nodes[50]; 
    int n; 
} GRAPH; 

//QUEUE is also a struct, but no need to paste it here 

void bfs(GRAPH g, int start) { 
    QUEUE queue; 
    queue.f = -1; 
    queue.r = 0; 
    int v; //will hold the index of the node taken off the queue 
      //   (the one that's processed) 
    int visited[MAX] = {0}; 
    visited[start] = 1; 

    addToQueue(&queue, start);  //first node is visited, goes to queue 

    while (deleteFromQueue(&queue, &v)) { 
     printf("%d. ", v+1); 
     printStudent(g.nodes[v].s); 

     GRAPH_NODE *current = g->nodes[v]; 
     current->index = v; //not sure if this is right   

     //this is the part I'm suspicious about 
     while (current) { 
      int u = current->index; 
      if (!visited[u]) { 
       visited[u] = 1; 
       addToQueue(&queue, u); 
      } 
      current = current->next; 
     } 
    } 
} 

Answer 1

Je ne vois rien de mal de façon flagrante, mais la structure graphique vous montre ici est trop simple à se soucier de BFS. Chaque nœud a au plus un front sortant: le pointeur next. C'est juste une liste liée, qui a seulement une traversée; largeur-première et profondeur-première sont équivalentes car il n'y a qu'un seul nœud au maximum à chaque profondeur.

Donc, vous n'avez vraiment besoin que de cette boucle interne "suspecte", elle commencera à partir d'un noeud et suivra les bords jusqu'à la fin de la liste chaînée.