Eukerian Path (Hierholzer's Algorithm)

Explanation

- **Eulerian Path** in a graph is a path that visits every edge exactly once. **Hierholzer's Algorithm** is used to find Eulerian paths or circuits in a graph.
-
- An Eulerian **Circuit** exists if all vertices have an even degree. An **Eulerian Path** exists if exactly two vertices have an odd degree.

-

• Steps:

  • Start at any vertex with an odd degree (if an Eulerian path is sought) or any vertex with an even degree (if an Eulerian circuit is sought).
  • Follow edges, marking them as used, until you have visited all edges.
  • If stuck, backtrack to earlier vertices and continue exploring unused edges.

• Time Complexity:

  • Time complexity: O(E), where E is the number of edges in the graph.