Implementation (Part 1)
Lektion 5 von 9 im Kurs Prims Algorithmus - Graphenalgorithmen von Coddy.
Wir beginnen mit der günstigsten Kante, die von einem Knoten ausgeht, Prims erster Schritt.
Aufgabe
EinfachPrims allererster Schritt besteht darin, die Kanten zu betrachten, die vom Startknoten ausgehen. Lassen Sie uns diese Suche aufbauen.
Schreiben Sie eine Funktion namens minEdgeFrom, die das flache edges-Array (Tripel [u, v, w, ...], ungerichtet) und einen Knoten node entgegennimmt und das kleinste Gewicht aller Kanten zurückgibt, die node berühren. Wenn node keine Kanten hat, geben Sie -1 zurück.
Zum Beispiel gibt minEdgeFrom([0,1,5, 0,2,3, 1,2,1], 0) den Wert 3 zurück.
Probier es selbst
#include <stdlib.h>
int minEdgeFrom(int* edges, int edges_size, int node) {
// Code hier schreiben
return -1;
}
Teste dich selbstDiese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.
Alle Lektionen in Prims Algorithmus - Graphenalgorithmen
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity