Tiefensuche
Lektion 11 von 14 im Kurs Graphen - Datenstrukturen-Serie #9 von Coddy.
Tiefensuche (Depth-First Search) geht in die Tiefe, bevor sie in die Breite geht. Ausgehend von einem Knoten folgt sie einer Kante so weit wie möglich, geht dann zurück und versucht die nächste. Die iterative Version verwendet einen Stack: Entnehme einen Knoten (pop), zeichne ihn auf und lege seine unbesuchten Nachbarn wieder ab (push).
Um sicherzustellen, dass die Tiefensuche in dieser Herausforderung eine deterministische Traversierungsreihenfolge erzeugt, füge die Nachbarn in umgekehrt sortierter Reihenfolge hinzu (push). Auf diese Weise landet der kleinste Nachbar oben auf dem Stack und wird zuerst verarbeitet, was der Reihenfolge entspricht, die eine rekursive Tiefensuche über aufsteigend sortierte Nachbarn erzeugen würde.
Achte darauf, dass ein Knoten nicht zweimal hinzugefügt wird (verschiedene Nachbarn können denselben Nachbarn haben). Überprüfe das Set der besuchten Knoten (visited set) am Anfang der Schleife und überspringe den Knoten, falls er bereits besucht wurde.
Aufgabe
EinfachSchreibe eine Funktion dfs, die ein 2D-Int-Array adjacency (jede Zeile ist eine [u, v] Kante) und einen Int start erhält und die DFS-Besuchsreihenfolge von start als eine Liste von Ints zurückgibt.
Baue den Graphen auf, indem du jede Kante hinzufügst. Iterative DFS unter Verwendung eines Stacks: Entnimm einen Knoten, falls er noch nicht besucht wurde, zeichne ihn auf und lege seine Nachbarn in umgekehrt sortierter Reihenfolge ab, sodass der kleinste zuerst verarbeitet wird.
Du musst die Klasse Graph verwenden (bereitgestellt in graph) – verwende keine in der Sprache eingebauten Strukturen (Maps, Sets), um die Adjazenz zu modellieren. Hilfsdaten für den Algorithmus (Visited-Sets, Stacks) dürfen stdlib-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 = dfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}