Umfassender Leitfaden zu 23+ essentiellen Graphalgorithmen mit Komplexitätsanalyse, Anwendungsfällen und interaktiven Visualisierungen.
Interaktive Plattform TestenErkundet den Graphen Ebene für Ebene und besucht alle Nachbarn, bevor er tiefer geht. Verwendet eine Warteschlange zur Aufrechterhaltung der Erkundungsreihenfolge.
Erkundet so tief wie möglich entlang jedes Zweigs, bevor er zurückverfolgt. Verwendet einen Stapel (oder Rekursion) zur Verfolgung des Erkundungspfads.
Lineare Anordnung von Knoten in einem gerichteten azyklischen Graphen (DAG), bei der jeder Knoten vor allen Knoten erscheint, auf die er zeigt.
Findet einen Pfad, der jede Kante genau einmal in einem ungerichteten Graphen besucht. Existiert, wenn der Graph genau 0 oder 2 Knoten mit ungeradem Grad hat.
Findet kürzeste Pfade von einem Quellknoten zu allen anderen Knoten in einem gewichteten Graphen mit nicht-negativen Kantengewichten.
Findet kürzeste Pfade von einem Quellknoten und erkennt negative Gewichtszyklen. Funktioniert mit negativen Kantengewichten.
Findet kürzeste Pfade zwischen allen Knotenpaaren mittels dynamischer Programmierung mit Zwischenknoten.
Baut den minimalen Spannbaum durch Wachstum von einem einzelnen Knoten auf und fügt immer die Kante mit minimalem Gewicht hinzu, die zu einem neuen Knoten führt.
Baut den minimalen Spannbaum durch Sortierung aller Kanten und Verwendung von Union-Find zur Zyklusvermeidung beim Hinzufügen minimaler Gewichtskanten auf.
Baut den minimalen Spannbaum mit einem parallelen komponentenbasierten Ansatz auf, geeignet für verteilte Rechenumgebungen.
Findet stark zusammenhängende Komponenten in gerichteten Graphen mit DFS unter Verwendung von Low-Link-Werten und einem Stapel.
Findet stark zusammenhängende Komponenten mit zwei DFS-Durchläufen: einem auf dem ursprünglichen Graphen und einem auf dem transponierten Graphen.
Findet Knoten, deren Entfernung die Anzahl der zusammenhängenden Komponenten in einem ungerichteten Graphen erhöhen würde.
Findet Kanten, deren Entfernung die Anzahl der zusammenhängenden Komponenten in einem ungerichteten Graphen erhöhen würde.
Bestimmt, ob ein Graph mit genau zwei Farben gefärbt werden kann, sodass keine benachbarten Knoten dieselbe Farbe haben.
Erkennt das Vorhandensein von Zyklen in gerichteten und ungerichteten Graphen mit verschiedenen Techniken wie DFS und Union-Find.
Findet einen Pfad, der jeden Knoten genau einmal besucht, unter Verwendung von Backtracking- und dynamischen Programmiertechniken.
Findet die kürzeste mögliche Route, die jede Stadt genau einmal besucht und zum Ausgangspunkt zurückkehrt.
Weist Knoten Farben zu, sodass keine zwei benachbarten Knoten dieselbe Farbe haben, unter Verwendung der minimalen Anzahl von Farben.
Findet den größten vollständigen Teilgraphen, in dem jedes Knotenpaar durch eine Kante verbunden ist.
Bestimmt, ob ein Graph chordal ist (jeder Zyklus der Länge 4 oder mehr hat eine Sehne - eine Kante, die zwei nicht benachbarte Knoten im Zyklus verbindet).
Findet den maximalen Fluss von einer Quelle zu einer Senke in einem Flussnetzwerk mit Algorithmen wie Ford-Fulkerson mit erweiternden Pfaden.
Findet den Schnitt mit minimaler Kapazität, der die Quelle von der Senke trennt, eng verwandt mit dem maximalen Fluss durch das Max-Flow-Min-Cut-Theorem.
Erleben Sie interaktive Visualisierungen und schrittweise Ausführung aller dieser Algorithmen.
Interaktive Plattform Starten