Implementation (Part 1)
Leçon 5 sur 9 du cours Algorithme de Prim - Algorithmes de graphes de Coddy.
Nous commençons par l'arête la moins coûteuse partant d'un sommet, le premier mouvement de Prim.
Défi
FacileLe tout premier mouvement de Prim consiste à examiner les arêtes partant du sommet de départ. Construisons cette recherche.
Écrivez une fonction nommée minEdgeFrom qui prend le tableau plat edges (triplets [u, v, w, ...], non orienté) et un sommet node, et renvoie le plus petit poids parmi toutes les arêtes touchant node. Si node n'a pas d'arêtes, renvoyez -1.
Par exemple, minEdgeFrom([0,1,5, 0,2,3, 1,2,1], 0) renvoie 3.
Essayez vous-même
#include <stdlib.h>
int minEdgeFrom(int* edges, int edges_size, int node) {
// Écrire le code ici
return -1;
}
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 Algorithme de Prim - Algorithmes de graphes
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity