BFS
Leçon 10 sur 14 du cours Graphes - Série Structures de données n°9 de Coddy.
Les prochains défis sont conçus pour utiliser la classe Graph que vous venez de construire.
Chaque défi vous fournit un fichier graph verrouillé (le Graph final du chapitre précédent) et un nouveau fichier solution dans lequel vous écrirez une fonction qui UTILISE le Graph.
Notre premier algorithme : Parcours en largeur (Breadth-First Search). À partir d'un sommet, le BFS visite tous les sommets accessibles par vagues : d'abord le point de départ, puis tout ce qui se trouve à une arête de distance, puis tout ce qui se trouve à deux arêtes, et ainsi de suite. L'implémentation classique utilise une file d'attente (queue) : enfilez le point de départ, puis défilez de manière répétée, enregistrez le sommet comme visité et enfilez tous les voisins non visités.
Comme les listes de voisins n'ont pas d'ordre fixe, deux exécutions correctes du BFS peuvent produire des ordres de parcours différents. Pour rendre la réponse déterministe dans ce défi, triez les voisins de chaque sommet par ordre croissant avant de les enfiler.
Défi
FacileÉcrivez une fonction bfs qui reçoit un tableau d'entiers 2D adjacency (chaque ligne est une arête [u, v]) et un entier start, et renvoie l'ordre de visite BFS à partir de start sous forme d'une liste d'entiers.
Construisez le graphe : pour chaque [u, v] dans adjacency, appelez g.addEdge(u, v). Ensuite, effectuez un parcours BFS à partir de start en utilisant une file d'attente (queue). Lors du traitement des voisins d'un sommet, triez-les par ordre croissant afin que la sortie soit déterministe.
Vous devez utiliser la classe Graph (fournie dans graph) - n'utilisez pas les types intégrés du langage (maps, sets) pour modéliser l'adjacence. Les données auxiliaires pour l'algorithme (ensembles de sommets visités, files d'attente) peuvent utiliser les types de la bibliothèque standard (stdlib).
Essayez vous-même
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start;
if (scanf("%d %d %d", &n, &m, &start) != 3) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
int out[MAX_VERTICES];
int outn = bfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}