GraphalgorithmenIntermediate
Zykluserkennung (Floyds Algorithmus)
Auch als 'Schildkrote und Hase'-Algorithmus bekannt, erkennt diese elegante Technik Zyklen in verketteten Listen oder Sequenzen mit O(1) Speicher. Verwendet zwei Zeiger, die sich mit unterschiedlichen Geschwindigkeiten bewegen - wenn es einen Zyklus gibt, werden sie sich schliesslich treffen. Wesentlich fur die Erkennung von Endlosschleifen, Analyse von Graphstrukturen und Validierung der Datenintegritat.
#graph#dfs#cycle-detection#dependency-resolution
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
How it works
- • Uses DFS with recursion stack
- • White nodes: unvisited
- • Gray nodes: in recursion stack
- • Black nodes: completed
- • Cycle found when back edge detected
Step: 1 / 0
500ms
SlowFast
Keyboard Shortcuts
Space Play/Pause← → StepR Reset1-4 Speed
Real-time Statistics
Algorithm Performance Metrics
Progress0%
Comparisons
0
Swaps
0
Array Accesses
0
Steps
1/ 0
Algorithm Visualization
Step 1 of 0
Initialize array to begin
Default
Comparing
Swapped
Sorted
Code Execution
Currently executing
Previously executed
Implementation