Shortest Walk Through Every Node
Problem
A connected undirected graph has n nodes, numbered 0 to n - 1, where n is at most 12, given as adjacency lists. Return the fewest edges in a walk that visits every node at least once. The walk may start and end at any nodes, and it may repeat both nodes and edges.
Examples
Input: adj = [[1, 3, 4], [0, 2], [1, 3, 5], [2, 0], [0], [2]]
Output: 6
Why: a square 0-1-2-3 with a leaf on 0 and a leaf on 2;
4-0-1-2-3-2-5 has to step back through 2 onceInput: adj = [[1, 2], [0, 2, 5], [0, 1, 3], [2, 4], [3], [1]]
Output: 5
Why: 5-1-0-2-3-4 touches all six nodes without repeating oneInput: adj = [[]]
Output: 0
Why: edge case, a single node is visited before any step is takenHints
0 / 3
The shortest walk depends on more than where you are: it also depends on which nodes you have already seen. Where you stand plus what you have seen is the real state.
With at most 12 nodes, the set of visited nodes fits in the bits of one integer, so a state is a pair of a node and a bitmask, and there are at most 12 times 4096 of them.
Run a breadth-first search over states, starting from every node at once with only its own bit set and distance 0. Moving along an edge to u sets bit u. The first time any state has every bit set, its distance is the answer.
Solution
A state is the current node together with the bitmask of visited nodes, and moving along any edge costs 1, so breadth-first search over states finds the fewest steps. Starting from every node with distance 0 lets the walk begin anywhere, and the first state whose mask is full gives the answer, wherever it ends. Revisiting nodes is allowed because the same node with a different mask is a different state, while the same node with the same mask is never queued twice. Time is O(2ⁿ times the number of edges), and space is O(n 2ⁿ) for the visited states.
from collections import deque
def shortest_full_walk(adj):
n = len(adj)
full = (1 << n) - 1
starts = [(v, 1 << v) for v in range(n)]
seen = set(starts)
queue = deque((v, mask, 0) for v, mask in starts) # every node is a start
while queue:
v, mask, steps = queue.popleft()
if mask == full:
return steps
for u in adj[v]:
state = (u, mask | 1 << u) # stepping to u marks it visited
if state not in seen:
seen.add(state)
queue.append((u, state[1], steps + 1))
print(shortest_full_walk([[1, 3, 4], [0, 2], [1, 3, 5], [2, 0], [0], [2]])) # -> 6
print(shortest_full_walk([[1, 2], [0, 2, 5], [0, 1, 3], [2, 4], [3], [1]])) # -> 5
print(shortest_full_walk([[]])) # -> 0Stuck on the idea rather than the code? Bitmask as a Set covers it.