Tiefensuche

Sei ein Graph und . Die Tiefensuche beginnt am Knoten .

• Statt in die Breite zu gehen, wird so tief wie möglich in den Graphen gegangen.
• Dabei wird ein möglichst langer Pfad vom Startknoten aufgebaut.
• Der Pfadaufbau endet, wenn keine Nachfolger mehr zu finden sind oder bereits alle Nachfolger besucht wurden.
• Tiefensuche erlaubt einen eleganten, rekursiven Algorithmus
• Jeder Knoten bekommt zwei Zeitstempel:
  • firsttime - Knoten wurde zum ersten mal gesehen - grau
  • lasttime - Adjazenzliste des Knotens ist verarbeitet - schwarz

Implementierung

JavaScript

function dfs(graph, node, visited = new Set()) {
    if (visited.has(node)) {
        return; // Wenn der Knoten bereits besucht wurde, kehre zurück
    }
 
    visited.add(node); // Markiere den Knoten als besucht "grau"
    console.log(node); // Bearbeite den Knoten (hier einfach Ausgabe)
 
    // Rekursiver Aufruf für alle Nachbarn des Knotens
    graph[node].forEach(neighbor => {
        dfs(graph, neighbor, visited);
    });
 
	// Adjazenzliste ist abgearbeitet, "schwarz"
}

Komplexität

• Aufwand für die Initialisierung:
• Für einen Knoten wird maximal einmal dfs aufgerufen, d.h. es gibt viele Aufrufe der Funktion
• Innerhalb von dfs wird jede Adjazenzliste maximal einmal durchlaufen, insgesamt gibt es Einträge in allen Listen
• Insgesamt ergibt sich: