Breitensuche
Lektion 10 von 14 im Kurs Graphen - Datenstrukturen-Serie #9 von Coddy.
Die nächsten Herausforderungen sind darauf ausgelegt, die Graph-Klasse zu verwenden, die Sie gerade erstellt haben.
Jede Herausforderung liefert Ihnen eine gesperrte graph-Datei (der finale Graph aus dem vorherigen Kapitel) und eine neue solution-Datei, in der Sie eine Funktion schreiben, die den Graph VERWENDET.
Unser erster Algorithmus: Breadth-First Search (Breitensuche). Ausgehend von einem Knoten besucht BFS alle erreichbaren Knoten in Wellen: zuerst den Startknoten, dann alles, was eine Kante entfernt ist, dann alles, was zwei Kanten entfernt ist, und so weiter. Die klassische Implementierung verwendet eine queue: Fügen Sie den Startknoten in die Queue ein, nehmen Sie dann wiederholt Elemente aus der Queue heraus, markieren Sie den Knoten als besucht und fügen Sie alle nicht besuchten Nachbarn in die Queue ein.
Da Nachbarlisten keine feste Reihenfolge haben, können zwei korrekte BFS-Durchläufe unterschiedliche Traversierungsreihenfolgen erzeugen. Um die Antwort in dieser Herausforderung deterministisch zu machen, sortieren Sie die Nachbarn jedes Knotens aufsteigend, bevor Sie sie in die Queue einfügen.
Aufgabe
EinfachSchreiben Sie eine Funktion bfs, die ein 2D-Int-Array adjacency (jede Zeile ist eine [u, v] Kante) und einen Int start erhält und die BFS-Besuchsreihenfolge von start als Liste von Ints zurückgibt.
Bauen Sie den Graphen auf: Rufen Sie für jedes [u, v] in adjacency die Methode g.addEdge(u, v) auf. Führen Sie dann eine BFS von start unter Verwendung einer Queue durch. Wenn Sie die Nachbarn eines Knotens verarbeiten, sortieren Sie diese aufsteigend, damit die Ausgabe deterministisch ist.
Sie müssen die Klasse Graph verwenden (bereitgestellt in graph) - verwenden Sie keine in der Sprache eingebauten Typen (Maps, Sets), um die Adjazenz zu modellieren. Hilfsdaten für den Algorithmus (Visited-Sets, Queues) dürfen Standardbibliotheks-Typen verwenden.
Probier es selbst
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start;
if (scanf("%d %d %d", &n, &m, &start) != 3) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
int out[MAX_VERTICES];
int outn = bfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}