Using every edge exactly once

A different kind of path problem, with a traversal that looks wrong until you see why it works.

Why it works

Record a node only when it has nothing left

The repair is to build the route in reverse. Walk forward taking edges greedily. When a node has no unused edges left, it is a dead end, so add it to the output and step back. Reverse the whole output at the end.

The invariant that makes it work: a node is only recorded once every edge out of it has been used. So the recorded order is the reverse of a valid route, and reversing it produces one that uses every edge.

Getting stuck is no longer a failure. It is the signal to record and back up, and the walk resumes from wherever there are still unused edges.

On a graph with no choices at all the mechanism is easy to watch. The stack is on the left and the output being built is on the right.

1graph = {"a": ["b"], "b": ["c"], "c": []}2 3stack = ["a"]4out = []5while stack:6    if graph[stack[-1]]:7        stack.append(graph[stack[-1]].pop())8    else:9        out.append(stack.pop())             # nothing left here, record it10    print(stack, out)

The output comes out backwards, deepest dead end first, so the last step is to reverse it.

Predict the output· 5 min

Predict the output: taking the smallest option cheaply

Each node's destinations are stored so that removing the last one always hands back the smallest. Type the three lines it prints.

Python

1from collections import defaultdict2 3pairs = [("A", "C"), ("A", "B"), ("B", "C")]4 5graph = defaultdict(list)6for origin, destination in sorted(pairs, reverse=True):7    graph[origin].append(destination)8 9print(dict(graph))10print("next from A:", graph["A"].pop())11print("then from A:", graph["A"].pop())

Printed output

Problem· 32 min

Reconstruct Itinerary

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1graph = {"a": ["b"], "b": ["c"], "c": []}2 3stack = ["a"]4out = []5while stack:6 if graph[stack[-1]]:7 stack.append(graph[stack[-1]].pop())8 else:9 out.append(stack.pop()) # nothing left here, record it10 print(stack, out)

1from collections import defaultdict2 3pairs = [("A", "C"), ("A", "B"), ("B", "C")]4 5graph = defaultdict(list)6for origin, destination in sorted(pairs, reverse=True):7 graph[origin].append(destination)8 9print(dict(graph))10print("next from A:", graph["A"].pop())11print("then from A:", graph["A"].pop())