Fabian Rohlik

dfsPseudo.java

Java

// Depth-First Search Pseudocode von der Übungsstunde, mit Pre und Postzahlen

static t = 1        // Globale Zeitvariable für Pre- und Post-Zeiten

DFS(Adj):
    n = Adj.length
    visited[1...n] = {false, ..., false}   // Markiert, ob ein Knoten schon besucht wurde

    pre[1...n] = {-1, ..., -1}             // Pre-Zeiten (Zeitpunkt des ersten Besuchs)
    post[1...n] = {-1, ..., -1}            // Post-Zeiten (Zeitpunkt, wenn alle Nachbarn fertig sind)

    // Durchlaufe alle Knoten, um auch unzusammenhängende Graphen vollständig zu erkunden
    for v = 1...n:
        if visited[v] == false:
            Path(v, Adj, visited, pre, post)


Path(v, Adj, visited, pre, post):
    visited[v] = true       // Knoten v wird als besucht markiert
    pre[v] = t              // Pre-Zeit setzen
    t += 1

    // Rekursiv alle unbesuchten Nachbarn besuchen
    for u in Adj[v]:
        if visited[u] == false:
            Path(u, Adj, visited, pre, post)

    post[v] = t             // Post-Zeit setzen, nachdem alle Nachbarn abgeschlossen sind
    t += 1

Related posts