Inhaltsverzeichnis
Dieser Spickzettel ist für zwei Momente gemacht: die letzte Stunde vor einem technischen Interview und die Mitte einer Programmiersitzung, wenn Sie die Form des Problems kennen, aber das genaue Werkzeug brauchen. Er ist bewusst kompakt. Für die ganze Geschichte hinter jedem Algorithmus folgen Sie den Links zu den ausführlichen Artikeln, und wenn Sie einen strukturierten Weg durch alles möchten, beginnen Sie mit dem Graphentheorie-Lernpfad.
Durchgehend ist V die Anzahl der Knoten und E die Anzahl der Kanten.
Die große Komplexitätstabelle
Das mit Abstand Nützlichste, das man auswendig können sollte. Die Komplexitäten gehen von der üblichen effizienten Implementierung aus (binärer Heap für Dijkstra und Prim, Pfadkompression und Union by Rank für Union-Find).
| Algorithmus | Am besten für | Zeit | Speicher |
|---|---|---|---|
| BFS | Kürzester Weg in ungewichteten Graphen, Ebenenordnung | O(V + E) | O(V) |
| DFS | Zusammenhang, Zyklen, Struktur erkunden | O(V + E) | O(V) |
| Dijkstra | Kürzester Weg, nichtnegative Gewichte | O((V + E) log V) | O(V) |
| Bellman-Ford | Kürzester Weg mit negativen Gewichten | O(V · E) | O(V) |
| Floyd-Warshall | Kürzeste Wege zwischen allen Paaren, kleine dichte Graphen | O(V³) | O(V²) |
| A* | Heuristischer kürzester Weg (Karten, Spiele) | O(E) typisch | O(V) |
| Kruskal | Minimaler Spannbaum, dünn besetzte Graphen | O(E log E) | O(V) |
| Prim | Minimaler Spannbaum, dichte Graphen | O((V + E) log V) | O(V) |
| Topological Sort | Einen DAG nach Abhängigkeiten ordnen | O(V + E) | O(V) |
| Union-Find | Dynamischer Zusammenhang, Gruppierung | O(α(V)) pro Operation | O(V) |
| Tarjan / Kosaraju | Starke Zusammenhangskomponenten | O(V + E) | O(V) |
| Edmonds-Karp | Maximaler Fluss, minimaler Schnitt | O(V · E²) | O(V + E) |
| Brauchen Sie den echten Code? Diese Tabelle listet 12 Grundlagen auf einen Blick. Das Algorithmen-Handbuch enthält alle 55, jeweils mit Pseudocode und Schritt für Schritt hergeleiteter Komplexität. | |||
Hinweis zu A*: seine Laufzeit hängt ganz von der Heuristik ab. Mit einer perfekten Heuristik läuft er fast geradewegs zum Ziel; mit einer nutzlosen sinkt er auf Dijkstra herab. Das α bei Union-Find ist die inverse Ackermann-Funktion, praktisch eine kleine Konstante für jede Eingabe, die Ihnen je begegnen wird. Für die Begründung jeder Zeile siehe den Leitfaden zur Komplexität von Graphenalgorithmen.
Graphendarstellungen
Vor jedem Algorithmus wählen Sie, wie der Graph gespeichert wird. Diese eine Entscheidung beeinflusst jede Komplexität oben.
| Darstellung | Speicher | Kantenabfrage | Am besten für |
|---|---|---|---|
| Adjazenzliste | O(V + E) | O(degree) | Dünn besetzte Graphen, die Standardwahl |
| Adjazenzmatrix | O(V²) | O(1) | Dichte Graphen, Abfragen in konstanter Zeit |
Faustregel: Greifen Sie zur Adjazenzliste, außer der Graph ist dicht oder Sie brauchen Kantenprüfungen in konstanter Zeit. Ein 2D-Gitter ist ein impliziter Graph, in dem jede Zelle ein mit ihren Nachbarn verbundener Knoten ist, sodass Sie oft gar keine explizite Darstellung brauchen.
Traversierung: BFS und DFS
Die beiden Algorithmen, auf denen alles andere aufbaut. Den vollständigen Vergleich lernen Sie in BFS vs DFS.
- BFS verwendet eine Warteschlange, erkundet Ebene für Ebene und findet den kürzesten Weg in einem ungewichteten Graphen. Schlüsselwörter: kürzester, minimale Schritte, nächster, Ebenenordnung.
- DFS verwendet einen Stapel (oft den Aufrufstapel der Rekursion), taucht tief ein und ist ideal für Zusammenhang, Zyklenerkennung und Backtracking. Schlüsselwörter: alle Wege, Erreichbarkeit, Regionen, erkunden.
Kürzeste Wege
Die häufigste Familie in Interviews und in der Praxis. Die richtige Wahl wird von den Kantengewichten bestimmt. Die vollständige Vertiefung finden Sie in kürzeste Wege verstehen.
| Situation | Verwenden | Warum |
|---|---|---|
| Ungewichtete Kanten | BFS | Erste Ankunft ist der kürzeste Weg |
| Nichtnegative Gewichte | Dijkstra | Gierig mit einem Min-Heap, hier immer korrekt |
| Negative Gewichte | Bellman-Ford | Relaxiert Kanten V-1 mal, erkennt negative Zyklen |
| Alle Paare auf einmal | Floyd-Warshall | Drei verschachtelte Schleifen, winziger Code, top bei kleinen Graphen |
| Sie haben eine Heuristik | A* | Dijkstra zum Ziel geführt, siehe A* |
Die klassische Falle: Lassen Sie Dijkstra niemals auf einem Graphen mit negativen Kanten laufen. Er legt einen Knoten zu früh als endgültig fest und kann ein falsches Ergebnis liefern. Greifen Sie stattdessen zu Bellman-Ford.
Minimale Spannbäume
Verbinden Sie jeden Knoten bei geringsten Gesamtkantenkosten. Beide Algorithmen sind korrekt; wählen Sie nach Graphendichte. Vollständige Durchläufe in minimale Spannbäume.
- Kruskal: sortiere alle Kanten, füge die billigste hinzu, die keinen Zyklus bildet, und nutze Union-Find zur Zyklusprüfung. Glänzt bei dünn besetzten Graphen.
- Prim: lasse einen einzigen Baum nach außen wachsen und füge stets die billigste ihn verlassende Kante hinzu, mit einer Prioritätswarteschlange. Glänzt bei dichten Graphen.
Ordnung und Zusammenhang
- Topologische Sortierung (Kahn oder DFS-basiert): erzeugt eine lineare Ordnung eines DAG, sodass jede Kante nach vorne zeigt. Das Werkzeug für Abhängigkeiten, Build-Reihenfolge und Ablaufplanung. Unmöglich, wenn ein Zyklus existiert, was genau die Art ist, einen zu erkennen.
- Union-Find (disjunkte Mengen): beantwortet "sind diese beiden in derselben Gruppe?" und vereinigt Gruppen in nahezu konstanter Zeit. Das Rückgrat von Kruskal und von Problemen des dynamischen Zusammenhangs.
- Starke Zusammenhangskomponenten (Tarjan oder Kosaraju): findet maximale Gruppen, in denen jeder Knoten jeden anderen erreicht, in einem gerichteten Graphen. Beide laufen in
O(V + E).
Alle drei tauchen ständig in Interviews auf. Siehe die ausgearbeiteten Muster in essenzielle Graphenalgorithmen für Programmierinterviews.
Netzwerkfluss
Modellieren Sie Durchsatz, Matching und Engpässe. Das elegante Ergebnis hier ist, dass der maximale Fluss gleich dem minimalen Schnitt ist. Vollständige Behandlung in Netzwerkfluss und das Max-Flow-Min-Cut-Theorem.
- Ford-Fulkerson: schiebe wiederholt Fluss entlang augmentierender Wege im Restgraphen. Einfach, aber seine Laufzeit hängt von den Flusswerten ab.
- Edmonds-Karp: Ford-Fulkerson, der augmentierende Wege mit BFS findet und eine saubere Schranke
O(V · E²)unabhängig von den Kapazitäten liefert.
Welchen Algorithmus soll ich verwenden?
Der schnellste Weg, diesen Spickzettel zu nutzen: linke Spalte lesen, nach rechts springen.
| Wenn Sie … | Greifen Sie zu |
|---|---|
| jeden Knoten besuchen oder erkunden | BFS oder DFS |
| den kürzesten Weg in einem ungewichteten Graphen finden | BFS |
| den kürzesten Weg mit nichtnegativen Gewichten finden | Dijkstra |
| negative Kantengewichte behandeln | Bellman-Ford |
| kürzeste Wege zwischen allen Paaren erhalten | Floyd-Warshall |
| einen schnellen Weg mit einer Heuristik finden (Karten, Spiele) | A* |
| alles zu minimalen Kosten verbinden | Kruskal oder Prim |
| Aufgaben nach ihren Abhängigkeiten ordnen | Topologische Sortierung |
| prüfen, ob zwei Knoten verbunden sind, oder Elemente gruppieren | Union-Find |
| Cluster in einem gerichteten Graphen finden | Tarjan oder Kosaraju (SCC) |
| Durchsatz maximieren oder einen Engpass finden | Edmonds-Karp (Max-Flow) |
Verwandeln Sie die Tabelle in Intuition
Ein Spickzettel sagt Ihnen, welcher Algorithmus; ihn laufen zu sehen sagt Ihnen, warum. Gehen Sie einen davon Schritt für Schritt auf einem Live-Graphen durch.
Algorithmen-Visualisierer öffnenHäufig gestellte Fragen
Wie hoch ist die Zeitkomplexität von Dijkstras Algorithmus?
Mit einem binären Heap (Prioritätswarteschlange) läuft Dijkstras Algorithmus in O((V + E) log V) Zeit und O(V) Speicher. Mit einem einfachen Array statt eines Heaps ist er O(V hoch 2), was bei dichten Graphen schneller sein kann.
Welchen Graphenalgorithmus sollte ich für kürzeste Wege verwenden?
Das hängt vom Graphen ab. Verwenden Sie BFS für ungewichtete Graphen, Dijkstra für nichtnegative Gewichte, Bellman-Ford bei negativen Gewichten, Floyd-Warshall für kürzeste Wege zwischen allen Paaren und A*, wenn Sie eine gute Heuristik haben (Karten und Spiele).
Sollte ich eine Adjazenzliste oder eine Adjazenzmatrix verwenden?
Verwenden Sie eine Adjazenzliste für dünn besetzte Graphen: Sie benötigt O(V + E) Speicher und ist die Standardwahl für die meisten Probleme. Verwenden Sie eine Adjazenzmatrix für dichte Graphen oder wenn Sie O(1) Kantenabfragen brauchen, auf Kosten von O(V hoch 2) Speicher.
Welche Graphenalgorithmen sollte ich für Programmierinterviews auswendig lernen?
Die fünf Kernalgorithmen sind BFS, DFS, Dijkstras Algorithmus, topologische Sortierung und Union-Find. Zusammen decken sie den Großteil der Graphenfragen in technischen Interviews ab.