Implementation (Part 2)
Leçon 6 sur 9 du cours Parcours en largeur - Algorithmes de graphes de Coddy.
Maintenant, nous parcourons le graphe par niveaux à l'aide d'une file d'attente.
Défi
MoyenMaintenant, construisez le parcours complet.
Écrivez une fonction nommée bfs qui prend n, le tableau plat edges (non orienté), et un sommet start, et renvoie l'ordre dans lequel le BFS visite les sommets à partir de start.
Construisez la liste d'adjacence (voisins triés par ordre croissant), puis utilisez une file d'attente : marquez et enfilez le point de départ, puis défilez de manière répétée un sommet, enregistrez-le et enfilez ses voisins non visités. Seuls les sommets accessibles depuis start sont visités.
Essayez vous-même
#include <stdlib.h>
int* bfs(int n, int* edges, int edges_size, int start, int* returnSize) {
// Écrivez votre code ici
*returnSize = 0;
return edges;
}
Testez-vousCette leçon comprend un petit quiz. Commencez la leçon pour y répondre et suivre votre progression.
Toutes les leçons de Parcours en largeur - Algorithmes de graphes
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity