Implementation (Part 1)
Lektion 5 von 9 im Kurs Tiefensuche - Graph-Algorithmen von Coddy.
Wir werden DFS ausgehend von der Adjazenz-Suche aufbauen.
Aufgabe
EinfachBevor wir einen Graphen durchlaufen, müssen wir die Nachbarn jedes Knotens kennen. Lassen Sie uns diese Abfrage aus der flachen Kantenliste erstellen.
Schreiben Sie eine Funktion namens getNeighbors, die das edges Array (flache Paare [u0, v0, u1, v1, ...], ungerichtet) und einen Knoten node entgegennimmt und die sortierte Liste der Nachbarn von node ohne Duplikate zurückgibt.
Zum Beispiel gibt getNeighbors([0,1, 0,2, 1,2, 3,0], 0) das Ergebnis [1, 2, 3] zurück.
Probier es selbst
#include <stdlib.h>
int* getNeighbors(int* edges, int edges_size, int node, int* returnSize) {
// Hier Code schreiben
*returnSize = 0;
return edges;
}
Teste dich selbstDiese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.
Alle Lektionen in Tiefensuche - Graph-Algorithmen
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity