#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/euler-paths-and-circuits/hierholzer-s-pseudocode

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/euler-paths-and-circuits/hierholzer-s-pseudocode

Repovive

Hierholzer's Pseudocode - Euler Paths and Circuits | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Hierholzer's Pseudocode

Step-by-step implementation.

function findEulerPath(graph, start):
    stack = [start]
    path = []

    while stack is not empty:
        v = stack.top()
        if v has unused edges:
            u = any neighbor with unused edge
            mark edge (v, u) as used
            stack.push(u)
        else:
            path.append(stack.pop())

    return path.reversed()

For undirected graphs, mark both directions when using an edge.

Time: $O(E)$ since each edge is visited exactly once. Space: $O(V + E)$ for the stack and path.

Space complexity is $O(E)$ for the data structures used.