An Eulerian path is a path in a graph that visits every edge exactly once. This is crucial because, in the itinerary reconstruction problem (LeetCode 332), each flight (or ticket) is an edge that must be used exactly once.
Types of Eulerian Graphs:
- Eulerian Path: A path that visits every edge exactly once. It exists if and only if exactly 0 or 2 vertices have an odd degree (number of incoming + outgoing edges).
- Eulerian Circuit: A path that visits every edge exactly once and starts and ends at the same vertex. It exists if and only if all vertices have an even degree.
Hierholzer’s Algorithm:
Hierholzer’s algorithm efficiently constructs an Eulerian path or circuit. It uses a stack and operates in an iterative manner to explore and construct the path. Step-by-Step Introduction to Hierholzer’s Algorithm:
Steps in Hierholzer’s Algorithm:
- Choose a Starting Node: Start from a node with an odd degree (or any node, if it’s a circuit).
- Follow Unused Edges:
- While there are unused edges, follow any edge from the current node and move to the next node.
- Keep tracking the path using a stack.
- Backtrack if Stuck: If you reach a node where all edges have already been used, backtrack using the stack and start exploring another part of the graph.
- Build the Path: Once you’ve used all edges and backtracked to the starting node, the Eulerian path or circuit is completed.