Graphen
- Bellman-Ford mit Warteschlange (Algorithmus 4.11)
Der warteschlangenbasierte Bellman-Ford-Algorithmus aus Sedgewick/Wayne, Algorithmus 4.11 (Listing 4.36 bis 4.38) – kürzeste Pfade auch mit negativen Gewichten, negative Zyklen werden erkannt, an tinyEWDn und tinyEWDnc wie in Abbildung 4.91 und 4.92.
- Kürzeste Pfade in azyklischen Digraphen (Algorithmus 4.10)
AcyclicSP aus Sedgewick/Wayne, Algorithmus 4.10 (Listing 4.34) – kürzeste Pfade in einem kantengewichteten DAG, Knoten für Knoten in topologischer Reihenfolge relaxiert, auch mit negativen Gewichten, am Digraphen tinyEWDAG wie in Abbildung 4.77.
- Kürzeste Pfade nach Dijkstra (Algorithmus 4.9)
Der Dijkstra-Algorithmus aus Sedgewick/Wayne, Algorithmus 4.9 (Listing 4.32) – kürzeste Pfade ab einem Startknoten in einem gerichteten, kantengewichteten Graphen, Knoten für Knoten aus einer indizierten Vorrangwarteschlange, am Digraphen tinyEWD wie in Abbildung 4.74.
- Minimaler Spannbaum nach Kruskal (Algorithmus 4.8)
Der MST-Algorithmus von Kruskal aus Sedgewick/Wayne, Algorithmus 4.8 (Listing 4.25) – alle Kanten nach Gewicht aus einer Vorrangwarteschlange, Union-Find verwirft jede, die einen Zyklus schlösse, am Graphen tinyEWG.
- Minimaler Spannbaum nach Prim (Algorithmus 4.7)
Der MST-Algorithmus von Prim in der Eager-Version aus Sedgewick/Wayne, Algorithmus 4.7 (Listing 4.24) – der Baum wächst ab Knoten 0, eine indizierte Vorrangwarteschlange hält je Knoten die beste Verbindung, am Graphen tinyEWG mit dem Ablauf aus Abbildung 4.61.
- Starke Komponenten nach Kosaraju (Algorithmus 4.6)
Der Kosaraju-Algorithmus aus Sedgewick/Wayne, Algorithmus 4.6 (Listing 4.17) – erst die umgekehrte Postorder des umgedrehten Digraphen, dann Tiefensuchen in genau dieser Reihenfolge, am Digraphen tinyDG.
- Topologisches Sortieren (Algorithmus 4.5)
Das topologische Sortieren aus Sedgewick/Wayne, Algorithmus 4.5 (Listing 4.16) – erst die Zyklussuche mit onStack[], dann die umgekehrte Postorder einer Tiefensuche, an den Vorrangbedingungen der Studienfächer aus jobs.txt.
- Erreichbarkeit in Digraphen (Algorithmus 4.4)
Die Erreichbarkeit in gerichteten Graphen aus Sedgewick/Wayne, Algorithmus 4.4 (Listing 4.13) – Tiefensuche entlang der Pfeile, ab einem oder mehreren Startknoten, am Digraphen tinyDG mit dem Ablauf aus Abbildung 4.32 und den drei Testläufen des Buchs.
- Zusammenhangskomponenten (Algorithmus 4.3)
Die Zusammenhangskomponenten aus Sedgewick/Wayne, Algorithmus 4.3 (Listing 4.8) – die for-Schleife des Konstruktors, je Komponente eine Tiefensuche, id[] und count Schritt für Schritt, dazu connected(v, w), am Graphen tinyG aus dem Buch.
- Breitensuche für Pfade (Algorithmus 4.2)
Die Breitensuche aus Sedgewick/Wayne, Algorithmus 4.2 (Listing 4.6) – Knoten für Knoten aus der Warteschlange, Abstände als Ebenen im Baum aus edgeTo[], kürzeste Pfade mit pathTo(v) und der direkte Vergleich mit der Tiefensuche am selben Graphen.
- Tiefensuche für Pfade (Algorithmus 4.1)
Die Tiefensuche aus Sedgewick/Wayne, Algorithmus 4.1 (Listing 4.5) – dfs Aufruf für Aufruf mit Aufrufstapel, marked[] und edgeTo[], der Baum aus edgeTo[] und pathTo(v) mit dem Stapel, am Graphen aus Abbildung 4.16.