DFS: Inseln und Zyklen

Code in:JavaC#PythonJavaScript

Kurz gesagt: DFS (Tiefensuche) folgt einem Weg, so weit er reicht, und geht dann zurück, mit Rekursion oder mit einem Stapel; sie findet Zusammenhangskomponenten und Zyklen in einem Graphen in O(V + E).

Problem

Eine Stadt, vom Fluss zerschnitten

Die Stadt sperrt beide Brücken wegen Bauarbeiten. Die Kuriere können den Fluss nicht mehr überqueren, und die Disposition muss wissen, in wie viele Teile die Stadt zerfällt und welche Haltestellen in welchem Teil liegen: Jeder Teil bekommt einen eigenen Lieferwagen.

Aus der BFS-Lektion weißt du, wie man findet, was vom Lager aus erreichbar ist. Es kann aber viele Teile geben, und jeder muss ganz gefunden werden. Du brauchst einen Gang, der bei jeder Haltestelle ohne Teil startet und alles markiert, was er erreicht.

In derselben Stadt gibt es ein zweites Problem. Der Lieferplan hat Regeln „A wird vor B beliefert“. Jemand hat eine falsche Regel dazugeschrieben, und jetzt gibt es keine Reihenfolge, die alle einhält. Welche Regel ist schuld?

Die Idee

So weit die Straße reicht

DFS (Tiefensuche) geht wie ein Mensch im Labyrinth: Sie nimmt die erste Straße zu einer unbekannten Haltestelle, von dort die erste zur nächsten unbekannten, und so weiter, bis sie eine Haltestelle erreicht, um die alles gesehen wurde. Dann geht sie eine Haltestelle zurück und probiert deren nächste Straße.

Bei der Rekursion passiert das Zurückgehen von selbst: visit für eine Haltestelle ruft visit für ihren ersten unbekannten Nachbarn auf, und wenn der fertig ist, läuft die Schleife mit dem nächsten weiter. Der Aufrufstapel merkt sich, wie weit jede Haltestelle ist.

• Jede Haltestelle bekommt die Nummer ihrer Insel, sobald sie betreten wird. Das ist zugleich die Menge der gesehenen Haltestellen: Eine Haltestelle mit Nummer wird nicht ein zweites Mal besucht.
• Eine Insel (eine Zusammenhangskomponente) ist alles, was ein visit erreicht. Die Schleife über alle Haltestellen startet von jeder Haltestelle ohne Nummer ein neues visit.

Sieh es dir an

Hinunter und zurück

static void Visit(Dictionary<string, List<string>> graph,
                  string stop, int island,
                  Dictionary<string, int> islandOf)
{
    islandOf[stop] = island;
    foreach (string next in graph[stop])
    {
        if (!islandOf.ContainsKey(next))
        {
            Visit(graph, next, island, islandOf);
        }
    }
}

static Dictionary<string, int> Islands(
    Dictionary<string, List<string>> graph, string[] stops)
{
    var islandOf = new Dictionary<string, int>();
    int count = 0;
    foreach (string stop in stops)
    {
        if (islandOf.ContainsKey(stop)) continue;
        count++;
        Visit(graph, stop, count, islandOf);
    }
    return islandOf;
}

static void Visit(Dictionary<string, List<string>> graph,
                  string stop, int island,
                  Dictionary<string, int> islandOf)
{
    islandOf[stop] = island;
    foreach (string next in graph[stop])
    {
        if (!islandOf.ContainsKey(next))
        {
            Visit(graph, next, island, islandOf);
        }
    }
}

static Dictionary<string, int> Islands(
    Dictionary<string, List<string>> graph, string[] stops)
{
    var islandOf = new Dictionary<string, int>();
    int count = 0;
    foreach (string stop in stops)
    {
        if (islandOf.ContainsKey(stop)) continue;
        count++;
        Visit(graph, stop, count, islandOf);
    }
    return islandOf;
}

Schritt für Schritt, in Worten

1. Beide Brücken sind gesperrt. islands geht die Haltestellen der Reihe nach durch: Lager hat noch keine Insel, also count = 1, und visit startet dort.
2. visit(Lager) gibt der Haltestelle Insel 1 und geht sofort in den ersten Nachbarn ohne Insel: Bahnhof. Lager wartet grau auf dem Aufrufstapel.
3. Immer tiefer: Bahnhof → Platz → Markt. Vier Aufrufe sind gleichzeitig offen, und jeder wartet auf den darüber.
4. Um Markt hat schon alles eine Insel. visit kehrt zurück, und Markt wird schwarz. Zurück im Stapel: Auch bei Platz und Bahnhof gibt es nichts Neues.
5. Lager ist wieder oben. Sein letzter Nachbar Markt ist schon gesehen, also endet der erste Gang: Insel 1 ist Lager, Bahnhof, Markt, Platz. Die gesperrten Brücken haben ihn am Fluss gestoppt.
6. Die Schleife in islands geht weiter: Bahnhof, Markt und Platz haben schon eine Insel und werden übersprungen. Park hat keine: count = 2.
7. Derselbe Gang am anderen Ufer: Park → Stadion → Krankenhaus → Kino, dann zurück zu Park.
8. Zwei Inseln: 4 Haltestellen an jedem Ufer. Jede Haltestelle bekam einmal eine Nummer, und jede Straße wurde von beiden Enden angesehen: O(V + E).

Das Programm sperrt die Brücken, startet Islands und gibt die Inseln aus:

(string, string)[] closed =
[
    ("Markt", "Park"), ("Platz", "Kino"),
];
foreach (var (a, b) in closed)
{
    graph[a].Remove(b);
    graph[b].Remove(a);
}
var islandOf = Islands(graph, stops);
int count = islandOf.Values.Max();
Console.WriteLine("Inseln: " + count);
for (int i = 1; i <= count; i++)
{
    var members = stops.Where(s => islandOf[s] == i);
    Console.WriteLine($"Insel {i}: {string.Join(", ", members)}");
}

Ausgabe

Inseln: 2
Insel 1: Lager, Bahnhof, Markt, Platz
Insel 2: Park, Kino, Krankenhaus, Stadion

Die Nummer der Insel steht in einem Dictionary<string, int>, und ihre Zahl ist die größte Nummer darin.

Probier es aus

Sag die Ausgabe voraus

Die Brücke Markt – Park ist offen, aber um das Kino sind Bauarbeiten: Platz – Kino und Kino – Krankenhaus sind gesperrt. Wie viele Inseln gibt das Programm aus?

(string, string)[] closed =
[
    ("Platz", "Kino"), ("Kino", "Krankenhaus"),
];
foreach (var (a, b) in closed)
{
    graph[a].Remove(b);
    graph[b].Remove(a);
}
var islandOf = Islands(graph, stops);
int count = islandOf.Values.Max();
Console.WriteLine("Inseln: " + count);

Antwort

Inseln: 3

Inseln: 2

Inseln: 1

Prüfen

Die Idee

Ein eigener Stapel statt Rekursion

Hier haben die Inseln je 4 Haltestellen, und die Rekursion ist 4 Aufrufe tief. In einer Rasterstadt mit 100.000 Kreuzungen kann ein Gang in die Tiefe zehntausende Ebenen hinabsteigen, und jede Ebene ist ein Frame auf dem Aufrufstapel. Der Stapel ist klein und läuft über. Wie aus der Rekursion eine Schleife wird, steht in der Lektion „Von der Rekursion zur Schleife“. Hier ist es dasselbe: Der Stapel wird zu einer gewöhnlichen Sammlung.

static List<string> Walk(Dictionary<string, List<string>> graph,
                         string start)
{
    var order = new List<string>();
    var seen = new HashSet<string>();
    var stack = new Stack<string>();
    stack.Push(start);
    while (stack.Count > 0)
    {
        string stop = stack.Pop();
        if (!seen.Add(stop)) continue;
        order.Add(stop);
        var next = graph[stop];
        for (int i = next.Count - 1; i >= 0; i--)
        {
            if (!seen.Contains(next[i])) stack.Push(next[i]);
        }
    }
    return order;
}

Zwei Dinge sind anders als bei der Rekursion:

• Eine Haltestelle kann zweimal auf den Stapel kommen: von zwei Nachbarn aus, bevor sie besucht wird. Darum wird die Prüfung „schon gesehen?“ auch beim Herausnehmen gemacht: Beim zweiten Mal wird sie übersprungen.
• Die Nachbarn kommen in umgekehrter Reihenfolge hinein. Was zuletzt hineinkommt, geht zuerst heraus, also muss der erste Nachbar oben liegen. So ist die Reihenfolge dieselbe wie bei der Rekursion:

var islandOf = new Dictionary<string, int>();
Visit(graph, "Lager", 1, islandOf);
Console.WriteLine("Rekursion: " + string.Join(", ", islandOf.Keys));
Console.WriteLine("Eigener Stapel: " + string.Join(", ", Walk(graph, "Lager")));

Ausgabe

Rekursion: Lager, Bahnhof, Platz, Markt, Park, Stadion, Krankenhaus, Kino
Eigener Stapel: Lager, Bahnhof, Platz, Markt, Park, Stadion, Krankenhaus, Kino

Genauer, für Neugierige

Wenn du die Nachbarn in der Reihenfolge der Liste hineinlegst, ist der Gang immer noch eine Tiefensuche und findet dieselben Inseln, nur die Reihenfolge der Besuche ist anders. Für die Inseln spielt die Reihenfolge keine Rolle. Für die Zyklen in einem gerichteten Graphen weiter unten schon: Dort musst du wissen, wann jede Haltestelle fertig wird, und mit einem Stapel aus Haltestellen ist das schwerer. Darum ist findCycle rekursiv, und bei tiefen Graphen hält der Stapel ein Paar (Haltestelle, wie weit sie in ihrer Liste ist).

Die Idee

Ein Zyklus im Lieferplan

Die Regeln des Plans sind ein gerichteter Graph: Der Pfeil Markt → Park heißt „Markt vor Park“. Bilden die Pfeile einen Zyklus, gibt es keine Reihenfolge, die sie einhält: Jede Haltestelle im Zyklus müsste vor sich selbst kommen.

„Gesehen“ allein reicht nicht, um einen Zyklus zu fangen. Markt → Platz führt zu einer gesehenen Haltestelle, aber es gibt keinen Zyklus: Von Platz kommst du nicht zurück zu Markt. Darum haben Haltestellen drei Farben:

• weiß: noch nicht gesehen;
• grau: auf dem aktuellen Pfad, ihr Aufruf ist noch offen;
• schwarz: alles danach ist geprüft, und es gibt keinen Zyklus.

Ein Pfeil auf eine graue Haltestelle führt zurück in den eigenen Pfad: Das ist der Zyklus.

static List<string>? FindCycle(
    Dictionary<string, List<string>> plan, string stop,
    Dictionary<string, string> color, List<string> path)
{
    color[stop] = "grey";
    path.Add(stop);
    foreach (string next in plan[stop])
    {
        string c = color.GetValueOrDefault(next, "white");
        if (c == "grey")
        {
            var cycle = path[path.IndexOf(next)..];
            cycle.Add(next);
            return cycle;
        }
        if (c == "white")
        {
            var found = FindCycle(plan, next, color, path);
            if (found != null) return found;
        }
    }
    color[stop] = "black";
    path.RemoveAt(path.Count - 1);
    return null;
}

static List<string>? FindCycle(
    Dictionary<string, List<string>> plan, string stop,
    Dictionary<string, string> color, List<string> path)
{
    color[stop] = "grey";
    path.Add(stop);
    foreach (string next in plan[stop])
    {
        string c = color.GetValueOrDefault(next, "white");
        if (c == "grey")
        {
            var cycle = path[path.IndexOf(next)..];
            cycle.Add(next);
            return cycle;
        }
        if (c == "white")
        {
            var found = FindCycle(plan, next, color, path);
            if (found != null) return found;
        }
    }
    color[stop] = "black";
    path.RemoveAt(path.Count - 1);
    return null;
}

Schritt für Schritt, in Worten

1. Jeder Pfeil ist eine Regel: Die Haltestelle, von der er ausgeht, wird zuerst beliefert. Alle Haltestellen sind weiß, keine wurde gesehen. Der Gang startet bei Lager.
2. Grau heißt auf dem aktuellen Pfad: Lager → Bahnhof → Platz. Diese Aufrufe sind noch offen.
3. Von Platz geht keine Regel aus: Platz wird schwarz, alles danach ist geprüft, und die Haltestelle verlässt den Pfad. Auch Bahnhof ist fertig.
4. Auch Markt zeigt auf Platz, aber Platz ist schwarz: Von dort gibt es keinen Weg zurück zu Markt. Zwei Regeln auf dieselbe Haltestelle sind kein Zyklus.
5. Hinter dem Fluss wächst der Pfad: Park → Kino → Krankenhaus → Stadion, alle grau.
6. Stadion → Park: Park ist grau, also noch auf dem Pfad. Der Pfeil führt zurück in den Pfad selbst, und das ist ein Zyklus.
7. Der Zyklus ist der Pfad von Park bis zum Ende: Park → Kino → Krankenhaus → Stadion → Park. Keine Reihenfolge dieser vier Haltestellen hält alle Regeln ein, also muss die Regel Stadion → Park weg.

Die Schleife startet findCycle von jeder weißen Haltestelle, so wie islands visit startet:

static List<string>? AnyCycle(
    Dictionary<string, List<string>> plan, string[] stops)
{
    var color = new Dictionary<string, string>();
    foreach (string stop in stops)
    {
        if (color.ContainsKey(stop)) continue;
        var found = FindCycle(plan, stop, color, []);
        if (found != null) return found;
    }
    return null;
}

(string, string)[] rules =
[
    ("Lager", "Bahnhof"), ("Bahnhof", "Platz"),
    ("Lager", "Markt"), ("Markt", "Platz"),
    ("Markt", "Park"), ("Park", "Kino"),
    ("Kino", "Krankenhaus"), ("Krankenhaus", "Stadion"),
    ("Stadion", "Park"),
];

var cycle = AnyCycle(plan, stops);
Console.WriteLine(cycle == null ? "Kein Zyklus" : "Zyklus: " + string.Join(" → ", cycle));

Ausgabe

Zyklus: Park → Kino → Krankenhaus → Stadion → Park

Entferne die letzte Regel, und das Programm gibt Kein Zyklus aus. Dann ist die Reihenfolge, in der die Haltestellen schwarz werden, die umgekehrte Lieferreihenfolge. Darauf baut die topologische Sortierung auf, die nächste Lektion.

static List<string>? FindCycle(
    Dictionary<string, List<string>> plan, string stop,
    Dictionary<string, string> color, List<string> path)
{
    color[stop] = "grey";
    path.Add(stop);
    foreach (string next in plan[stop])
    {
        string c = color.GetValueOrDefault(next, "white");
        if (c == "grey")
        {
            var cycle = path[path.IndexOf(next)..];
            cycle.Add(next);
            return cycle;
        }
        if (c == "white")
        {
            var found = FindCycle(plan, next, color, path);
            if (found != null) return found;
        }
    }
    color[stop] = ;
    path.RemoveAt(path.Count - 1);
    return null;
}

Prüfen

Genauer, für Neugierige

In einem ungerichteten Graphen ist jede Straße ein Pfeil in beide Richtungen, und der Nachbar, von dem du kamst, ist immer „gesehen“. Dort gibt es einen Zyklus, wenn du eine gesehene Haltestelle erreichst, die nicht die ist, von der du gerade kommst. Die drei Farben braucht man für einen gerichteten Graphen.

Die Idee

Was es kostet

Jede Haltestelle bekommt einmal eine Nummer und wird einmal besucht. Beim Besuch sieht sie ihre Straßen an, und eine Straße in beide Richtungen wird von beiden Enden gesehen. Insgesamt: V Besuche und 2E Blicke, O(V + E), wie bei BFS.

Linear ist es nur, wenn die Inselnummer vom ganzen Gang geteilt wird. Fragst du für jede Haltestelle „auf welcher Insel bin ich?“ mit einem neuen Gang und einer leeren Menge gesehener Haltestellen, machst du n Gänge. Lass beide in einer Rasterstadt mit n Kreuzungen laufen, die der Fluss in zwei Teile schneidet:

• Ein gemeinsames islandOf für die ganze Stadt O(n)
• Ein neuer Durchlauf für jede Kreuzung O(n²)

Algorithmus	n = 10	n = 1.000	n = 2.000	n = 100.000
Ein gemeinsames islandOf für die ganze Stadt	28	4.808	9.730	498.100
Ein neuer Durchlauf für jede Kreuzung	148	2.405.440	9.730.980	≈ 24.327.450.000

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

static Dictionary<string, int> Islands(
    Dictionary<string, List<string>> graph, string[] stops)
{
    var islandOf = new Dictionary<string, int>();
    int count = 0;
    foreach (string stop in stops)
    {
        if (islandOf.ContainsKey(stop)) continue;
        count++;
        Visit(graph, stop, count, islandOf);
    }
    return islandOf;
}

Gezählt wird jede Haltestelle, die vom Stapel genommen wird, und jeder Blick auf einen Nachbarn. Beide benutzen einen eigenen Stapel: Bei 100.000 Kreuzungen stürzt die Rekursion im Browser mit einem Stapelüberlauf ab. Bei 1000 Kreuzungen macht die geteilte Nummer 4.808 Operationen und ein neuer Gang für jede Kreuzung 2.405.440. Bei 2000 steht der neue Gang schon bei 9.730.980, während die geteilte Nummer bei 100.000 nur 498.100 braucht.

Probier es aus

Finde den Fehler

Ein Kollege hat entschieden, dass in visit die Insel mit jedem Schritt wachsen soll. Das Programm gibt aus:

static void Visit(Dictionary<string, List<string>> graph,
                  string stop, int island,
                  Dictionary<string, int> islandOf)
{
    islandOf[stop] = island;
    foreach (string next in graph[stop])
    {
        if (!islandOf.ContainsKey(next))
        {
            Visit(graph, next, island + 1, islandOf);
        }
    }
}

Ausgabe

Inseln: 5
Insel 1: Lager
Insel 2: Bahnhof, Park
Insel 3: Platz, Stadion
Insel 4: Markt, Krankenhaus
Insel 5: Kino

Es sind fünf Inseln, und Bahnhof und Park sind „auf einer Insel“, obwohl die Brücken gesperrt sind. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

1static void Visit(Dictionary<string, List<string>> graph,2 string stop, int island,3 Dictionary<string, int> islandOf)4{5 islandOf[stop] = island;6 foreach (string next in graph[stop])7 {8 if (!islandOf.ContainsKey(next))9 {10 Visit(graph, next, island + 1, islandOf);11 }12 }13}

Prüfen

Genauer

Wie tief Rekursion gehen kann

Der Stapel eines Threads in .NET ist etwa 1 MB groß. Ein Überlauf (StackOverflowException) lässt sich nicht abfangen: Der Prozess endet. Darum nimmt man für einen großen Graphen Stack<T>. Brauchst du trotzdem Rekursion, kannst du sie in einem Thread mit größerem Stapel laufen lassen.

Übung

Die kritischen Straßen

Löse die Aufgabe in deinem Editor.

Kritische Straßen. Die Brücke Markt – Park ist für einen Monat gesperrt, und Platz – Kino ist noch offen. Eine Straße ist kritisch, wenn ihre Sperrung die Stadt in mehr Inseln teilt. Sperre die Brücke und gib aus, wie viele Inseln es gibt. Dann nimm für jede offene Straße sie weg, zähle die Inseln mit islands und lege sie zurück. Gib die kritischen Straßen in der Reihenfolge von streets aus.

(string, string)[] closed =
[
    ("Markt", "Park"),
];

Ausgabe

Inseln: 1
Kritisch: Platz - Kino, Kino - Krankenhaus, Park - Stadion, Krankenhaus - Stadion

Weitere Aufgaben

• Die größte Insel. Gib die Insel mit den meisten Haltestellen aus und wie viele Lieferwagenstunden pro Woche sie braucht, wenn jede Haltestelle 3 Stunden dauert.
• Der Zyklus im Plan. Schreibe findCycle mit einem eigenen Stapel: Leg ein Paar (Haltestelle, Index des nächsten Nachbarn) auf den Stapel, und die Haltestelle wird schwarz, wenn der Index das Ende ihrer Liste erreicht.
• Inseln auf der Karte. Die Lagerkarte ist ein Raster aus # (Regal) und . (frei). Zähle die freien Zonen, wobei die Nachbarn einer Zelle oben, unten, links und rechts sind.

Test

Teste dich

1. Was macht DFS, wenn um die aktuelle Haltestelle schon alles gesehen wurde?

Es beendet den ganzen GangEs geht zu der Haltestelle zurück, von der es kam, und probiert deren nächsten NachbarnEs beginnt noch einmal beim Lager

2. Warum geht islands alle Haltestellen durch, statt visit nur vom Lager aus zu starten?

Um zu prüfen, ob visit richtig arbeitetEin visit erreicht nur seine eigene Insel; die Haltestellen hinter den gesperrten Brücken bleiben ohne NummerWeil die Reihenfolge der Haltestellen für DFS wichtig ist

3. Im gerichteten Plan sieht findCycle einen Pfeil auf eine schwarze Haltestelle. Ist das ein Zyklus?

Das hängt von der Reihenfolge der Regeln abNein: Die schwarze Haltestelle ist ganz geprüft, und von ihr gibt es keinen Weg zurück zur aktuellenJa: Die Haltestelle wurde schon gesehen

4. Die Stadt hat 100.000 Kreuzungen in einer langen Kette. Was passiert mit dem rekursiven visit?

Die Tiefe erreicht 100.000 Aufrufe, und der Stapel läuft über; du brauchst einen eigenen StapelNichts: Rekursion ist schnellEs funktioniert, ist aber O(V²)

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Der Aufrufstapel von innen · Von der Rekursion zur Schleife · Graph: Adjazenzliste und Matrix · BFS: die wenigsten Haltestellen
• Geht weiter in: Topologische Sortierung · Minimaler Spannbaum · Architektur-Review
• Aufgaben zum Thema: Graphen