Implementation (Part 2)
Lektion 6 von 9 im Kurs Breadth-First Search – Graph-Algorithmen von Coddy.
Jetzt durchlaufen wir den Graphen schichtweise mit einer Warteschlange.
Aufgabe
MittelErstellen Sie nun den vollständigen Durchlauf.
Schreiben Sie eine Funktion namens bfs, die n, das flache edges-Array (ungerichtet) und einen start-Knoten entgegennimmt und die Reihenfolge zurückgibt, in der BFS die Knoten von start aus besucht.
Erstellen Sie die Adjazenzliste (Nachbarn aufsteigend sortiert), verwenden Sie dann eine Warteschlange (Queue): Markieren Sie den Startknoten und fügen Sie ihn der Warteschlange hinzu, und entnehmen Sie wiederholt einen Knoten aus der Warteschlange, zeichnen Sie ihn auf und fügen Sie seine nicht besuchten Nachbarn der Warteschlange hinzu. Nur Knoten, die von start aus erreichbar sind, werden besucht.
Probier es selbst
#include <stdlib.h>
int* bfs(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 Breadth-First Search – Graph-Algorithmen
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity