GraphalgorithmenIntermediate

Topologische Sortierung

Ordnet Knoten eines gerichteten azyklischen Graphen (DAG) so, dass fur jede Kante u->v u vor v kommt. Verwendet DFS-basierten Ansatz. Wesentlich fur Abhangigkeitsauflosung, Build-Systeme und Kursplanung.

#graph#dag#dfs#dependency

Complexity Analysis

Time (Average)

O(V + E)

Expected case performance

Space

O(V)

Memory requirements

Time (Best)

O(V + E)

Best case performance

Time (Worst)

O(V + E)

Worst case performance

📚 CLRS Reference

Introduction to Algorithms•Chapter 22•Section 22.4

Step: 1 / 0

Animation Speed500ms

SlowFast

Keyboard Shortcuts

Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%

Comparisons

Swaps

Array Accesses

Steps

1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default

Comparing

Swapped

Sorted

Code Execution

Currently executing

Previously executed

Implementation

Related Algorithms

View all in Graphalgorithmen

Breitensuche (BFS)

Intermediate

Erkundet einen Graphen Ebene fur Ebene und besucht alle Knoten auf der aktuellen Tiefe, bevor er tiefer geht. Verwendet eine Warteschlange und ist ideal zum Finden kurzester Wege in ungewichteten Graphen. Anwendungen umfassen Labyrinthlosung, soziale Netzwerkanalyse und das Finden von Verbindungen zwischen Knoten.

Tiefensuche (DFS)

Intermediate

Erkundet einen Graphen, indem er so tief wie moglich entlang jedes Pfades geht, bevor er zuruckkehrt. Implementiert mit einem Stack oder Rekursion, was ihn naturlich fur rekursive Probleme macht. Wird fur Pfadfindung, Zykluserkennung, topologische Sortierung und Labyrinthgenerierung verwendet.

Dijkstras Algorithmus

Advanced

Findet die kurzesten Wege von einem einzelnen Quellknoten zu allen anderen Knoten in einem gewichteten Graphen. Treibt GPS-Navigationssysteme und Netzwerk-Routing-Protokolle an. Funktioniert effizient mit nicht-negativen Kantengewichten unter Verwendung eines Greedy-Ansatzes mit einer Priority Queue.

Back to Graphalgorithmen