Implementation (Part 2)
Lektion 6 von 9 im Kurs Tiefensuche - Graph-Algorithmen von Coddy.
Nun durchlaufen wir den gesamten Graphen mit einem Stack.
Aufgabe
MittelErstellen Sie nun die vollständige Traversierung.
Schreiben Sie eine Funktion namens dfs, die n, das flache edges-Array (ungerichtet) und einen start-Knoten entgegennimmt und die Reihenfolge zurückgibt, in der DFS die Knoten besucht, beginnend bei start.
Erstellen Sie zuerst die Adjazenzliste (sortieren Sie die Nachbarn jedes Knotens aufsteigend). Führen Sie dann eine iterative DFS mit einem Stack aus. Nur Knoten, die von start aus erreichbar sind, werden besucht.
Um Nachbarn in aufsteigender Reihenfolge zu besuchen, legen Sie diese vom größten zum kleinsten auf den Stack.
Probier es selbst
#include <stdlib.h>
int* dfs(int n, int* edges, int edges_size, int start, int* returnSize) {
// Code hier 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