Implementation (Part 2)
Leçon 6 sur 9 du cours Tri topologique - Algorithmes de graphes de Coddy.
Maintenant, nous supprimons de manière répétée les sommets de degré entrant 0 pour construire l'ordre.
Défi
MoyenMaintenant, construisez l'ordre complet.
Écrivez une fonction nommée topologicalSort qui prend n et le tableau plat edges (orienté u -> v), et renvoie un ordre topologique des sommets.
Utilisez l'algorithme de Kahn : calculez les degrés entrants, puis prenez de manière répétée le plus petit sommet ayant un degré entrant de 0, ajoutez-le, et réduisez le degré entrant de ses voisins sortants. Les entrées pour ce défi sont acycliques.
Prendre le plus petit sommet disponible à chaque étape rend la réponse unique.
Essayez vous-même
#include <stdlib.h>
int* topologicalSort(int n, int* edges, int edges_size, 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 Tri topologique - Algorithmes de graphes
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity