Erreichbarkeit in Digraphen (Algorithmus 4.4)

So geht’s: Beim Öffnen läuft die Tiefensuche ab Knoten 0 wie in Abbildung 4.32. Mit „Abspielen“ oder „Schritt“ geht es Aufruf für Aufruf. Orange ist der laufende dfs-Aufruf, orange umrandet sind die Aufrufe, die auf ihn warten (rechts als Aufrufstapel). Blau ist die Kante, die gerade geprüft wird. Kanten, über die die Suche weitergegangen ist, werden schwarz. Was am Ende grün ist, ist erreichbar, der Rest wird blass. Rechts unten entsteht das Protokoll im Stil der Abbildung („dfs(0)“, „prüfe 5“, „2 fertig“). Die Knöpfe oben spielen die drei Testläufe des Buchs nach: Bei 1 2 6 sieht man, dass der Bag die Startknoten rückwärts herausgibt und die erste Suche bei 6 beginnt. Mit „ab s“ lässt sich ein beliebiger Startknoten wählen, „Zufallsgraph“ erzeugt einen neuen Digraphen. „↺ Neu starten“ springt zurück zu Abbildung 4.32.

Erklärung

Erreichbarkeit in Digraphen (Algorithmus 4.4), Klasse DirectedDFS. Jetzt Abschnitt 4.2, gerichtete Graphen (Digraphen). Kanten haben eine Richtung: v→w heißt, man kommt von v nach w, aber nicht automatisch zurück.

Was sich ändert: Eigentlich nichts am Code. G.adj(v) liefert jetzt nur die Knoten, auf die v zeigt (ausgehende Kanten). Die Tiefensuche ist Wort für Wort dieselbe wie in [30], nur ohne edgeTo. Die Frage lautet: Welche Knoten sind von s aus erreichbar?

Der Code:

• marked[]: erreichbar ja/nein.
• Konstruktor 1: Tiefensuche ab einem Startknoten s.
• Konstruktor 2: ab einer Menge von Startknoten. Für jeden noch unmarkierten Startknoten eine Tiefensuche. Ergebnis: alles, was von irgendeinem der Startknoten erreichbar ist.
• marked(v): Ist v erreichbar?

Die Testläufe (tinyDG.txt):

• Start 1 → nur 1. Knoten 1 hat keine ausgehenden Kanten.
• Start 2 → 0 1 2 3 4 5.
• Start 1, 2, 6 → 0 1 2 3 4 5 6 9 10 11 12. Nur 7 und 8 sind nicht erreichbar.
• Asymmetrie: Von 0 kommt man zu 1, von 1 aber nicht zu 0. Im ungerichteten Graphen [32] wäre das unmöglich.

Abbildung 4.32 (Tiefensuche ab 0):

• dfs(0): Nachbarn 5 und 1, zuerst 5.
• dfs(5): Nachbar 4.
• dfs(4): Nachbarn 3 und 2, zuerst 3.
• dfs(3): prüfe 5 (schon markiert), dann 2 → dfs(2).
• dfs(2): prüfe 0, prüfe 3, beide markiert → 2 fertig.
• Zurück: 3 fertig, in 4 prüfe 2 (markiert), 4 fertig, 5 fertig.
• dfs(1): keine Nachbarn → 1 fertig, 0 fertig.
• Markiert: 0 bis 5. Die rechte Hälfte (6 bis 12) wird nie berührt, obwohl 6→0 eine Kante ist, denn sie zeigt in die falsche Richtung.

Satz D: Die Tiefensuche markiert alle von den Startknoten erreichbaren Knoten in Zeit proportional zur Summe der Ausgangsgrade der markierten Knoten.

Anwendung: Mark-and-Sweep-Speicherbereinigung:

• Objekte sind Knoten, Referenzen sind gerichtete Kanten.
• Startknoten sind die direkt zugänglichen Objekte (Variablen auf dem Stack, statische Felder).
• Phase 1 (Mark): genau diese Mehrfachstart-Tiefensuche, alles Erreichbare wird markiert.
• Phase 2 (Sweep): Alles Unmarkierte kann vom Programm nie mehr erreicht werden und wird freigegeben.
• Genau deshalb das null-Setzen gegen Loitering in [12] und [14]: Eine vergessene Referenz macht ein Objekt erreichbar, und der Garbage Collector darf es dann nicht abräumen.

Stand Kapitel 4:

• Algorithmus 4.1: Tiefensuche für Pfade [30]
• Algorithmus 4.2: Breitensuche für kürzeste Pfade [31]
• Algorithmus 4.3: Zusammenhangskomponenten [32]
• Algorithmus 4.4: Erreichbarkeit in Digraphen [33]