Euler Paths and Circuits
Visit every edge exactly once. Learn when Eulerian paths exist and how to find them.
Lessons
1. Intro
What you'll learn about Euler paths.
2. What is an Euler Path
Definition and examples.
3. What is an Euler Circuit
Euler path that returns to start.
4. Conditions for Undirected Graphs
When Euler paths exist in undirected graphs.
5. Conditions for Directed Graphs
When Euler paths exist in directed graphs.
6. Quiz: Euler Path Conditions
Knowledge check
7. Checking Eulerian Conditions
Algorithm to verify conditions.
8. Hierholzer's Algorithm
The standard algorithm for Euler paths.
9. Hierholzer's Pseudocode
Step-by-step implementation.
10. Why Hierholzer Works
Intuition behind the algorithm.
11. Quiz: Hierholzer's Algorithm
Knowledge check
12. Time and Space Complexity
Efficiency analysis.
13. Problem - Mail Delivery
CSES 1691 - Find Euler circuit.
14. Mail Delivery - Core idea
Check degrees and connectivity.
15. Mail Delivery - Algorithm
Apply Hierholzer from vertex 1.
16. Mail Delivery - Implementation
Code walkthrough.
17. Mail Delivery - Lessons
What you learned from this problem.
18. Quiz: Directed Euler Path Conditions
Knowledge check
19. Problem - Teleporters Path
CSES 1693 - Directed Euler path.
20. Teleporters Path - Core idea
Check in/out degree conditions.
21. Teleporters Path - Implementation
Code walkthrough.
22. Teleporters Path - Lessons
Directed vs undirected differences.
23. Problem - Reconstruct Itinerary
LeetCode 332 - Lexicographically smallest path.
24. Reconstruct Itinerary - Core idea
Sort and use Hierholzer.
25. Reconstruct Itinerary - Implementation
Code walkthrough.
26. Quiz: Lexicographic Euler Path
Knowledge check
27. De Bruijn Sequences
Visiting all n-bit strings.
28. Problem - De Bruijn Sequence
CSES 1692 - Construct the sequence.
29. De Bruijn Sequence - Core idea
Build De Bruijn graph and find Euler circuit.
30. De Bruijn Sequence - Implementation
Code walkthrough.
31. Quiz: De Bruijn Sequences
Knowledge check
32. Problem - Cracking the Safe
LeetCode 753 - De Bruijn application.
33. Cracking the Safe - Core idea
Generalized De Bruijn graph.
34. Chinese Postman Problem
When graph isn't Eulerian.
35. Applications
Where Euler paths appear.
36. Common Mistakes
Pitfalls to avoid.
37. Section Recap
Summary of Euler paths and circuits.