An Eulerian path in a graph is a path that traverses every edge of the graph exactly once. If the path ends at the same vertex where it started, it’s called an Eulerian cycle or Eulerian circuit. Finds a closed loop that covers all the edges in the graph.

Rules for Eulerian cycle:

1. In an undirected graph, either all nodes have an even degree, or exactly two have an odd degree.
2. In a directed graph, we need to check if:
   • Each node’s outDegree matches its inDegree.
   • Or, exactly one node has one more outgoing edge (outDegree = inDegree + 1), which indicates our starting point.

Fleury’s algorithm $O(E*E)$, which predates Hierholzer’s $O(E)$, is less efficient, which is why I will use the latter.

Python

def hierholzer_algorithm(graph):
    """Find Eulerian circuit in directed graph."""
    # represents the number of edges outgoing from a node
    edge_count = {node: len(edges) for node, edges in graph.items()}
    # store final circuit
    circuit = []
    # starting node
    curr_node = list(graph.keys())[0]
    # stack for backtracking and initialize with any node
    curr_path = [curr_node]

    while len(curr_path):
        # if an outgoing edge exists for current node
        if edge_count[curr_node]:
            # visit node and add to stack
            curr_path.append(curr_node)

            # find the next node using an edge
            next_node = graph[curr_node][-1]

            # remove the edge that was used
            edge_count[curr_node] -= 1
            graph[curr_node].pop()

            # move to next vertex
            curr_node = next_node
        # if no outgoing edge exists, backtrack to find remaining circuit
        else:
            # add current node with no outgoing edges to circuit
            circuit.append(str(curr_node))

            # backtrack by removing top element from stack
            curr_node = curr_path.pop()

    # print circuit in reverse
    print(" -> ".join(circuit[::-1]))

• Cracking The Safe
• Valid Arrangement Of Pairs