Existence check

Undirected: connected + all even degrees (circuit) or exactly 2 odd (path). Directed: connected + in/out equal (circuit) or 1 has out = in + 1 and 1 has in = out + 1 (path).

Advertisement

Hierholzer's algorithm

void hierholzer(int start) {
  Deque stack = new ArrayDeque<>();
  List circuit = new ArrayList<>();
  stack.push(start);
  while (!stack.isEmpty()) {
    int v = stack.peek();
    if (!adj[v].isEmpty()) {
      int u = adj[v].pollFirst();
      stack.push(u);
    } else {
      circuit.add(stack.pop());
    }
  }
  Collections.reverse(circuit);
}
Advertisement

Complexity

O(V + E). Linear in graph size.

Applications

DNA sequencing (Chinese Postman variant). Route planning. Circuit design.