Implementation (Part 2)
Leçon 6 sur 9 du cours Parcours en profondeur - Algorithmes de graphes de Coddy.
Maintenant, nous parcourons l'intégralité du graphe avec une pile.
Défi
MoyenMaintenant, construisez le parcours complet.
Écrivez une fonction nommée dfs qui prend n, le tableau plat edges (non orienté), et un sommet de départ start, et renvoie l'ordre dans lequel le DFS visite les sommets, en commençant par start.
Construisez d'abord la liste d'adjacence (triez les voisins de chaque sommet par ordre croissant). Ensuite, exécutez un DFS itératif avec une pile. Seuls les sommets accessibles depuis start sont visités.
Pour visiter les voisins dans l'ordre croissant, poussez-les sur la pile du plus grand au plus petit.
Essayez vous-même
#include <stdlib.h>
int* dfs(int n, int* edges, int edges_size, int start, int* returnSize) {
// Écrire 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