Implementation (Part 1)
Leçon 5 sur 9 du cours Parcours en profondeur - Algorithmes de graphes de Coddy.
Nous allons construire le DFS à partir de la recherche d'adjacence.
Défi
FacileAvant de parcourir un graphe, nous devons connaître les voisins de chaque sommet. Construisons cette recherche à partir de la liste d'arêtes à plat.
Écrivez une fonction nommée getNeighbors qui prend le tableau edges (paires à plat [u0, v0, u1, v1, ...], non orienté) et un sommet node, et renvoie la liste triée des voisins de node, sans doublons.
Par exemple, getNeighbors([0,1, 0,2, 1,2, 3,0], 0) renvoie [1, 2, 3].
Essayez vous-même
#include <stdlib.h>
int* getNeighbors(int* edges, int edges_size, int node, int* returnSize) {
// Écrivez le 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 profondeur - Algorithmes de graphes
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity