Seed (v, 1<<v) at distance zero for every vertex v. Multi-source BFS then explores all starting choices in the same distance order.

A state is (node,mask). An edge to v creates (v, mask | (1<<v)); this may keep the same mask when revisiting a node. A global set of full states prevents repeated work without incorrectly forbidding useful vertex revisits. Stop when the first dequeued state has all n bits set. Unit edges justify BFS even when the mask does not strictly increase; the acyclic exactly-once recurrence from subset DP cannot be copied unchanged.

What the function promises: graph is a connected undirected adjacency list on 0..n−1. Start and stop anywhere; vertices and edges may be reused. Return the fewest edges needed to visit all nodes. The helper returns −1 for disconnected nonempty input and zero for empty input.

from collections import deque

def shortest_visit_all(graph):
    n = len(graph)
    if n == 0:
        return 0
    complete = (1 << n) - 1
    queue = deque((u, 1 << u, 0) for u in range(n))
    seen = {(u, 1 << u) for u in range(n)}
    while queue:
        u, mask, steps = queue.popleft()
        if mask == complete:
            return steps
        for v in graph[u]:
            state = (v, mask | (1 << v))
            if state not in seen:
                seen.add(state)
                queue.append((v, state[1], steps + 1))
    return -1

assert shortest_visit_all([[1,2,3], [0], [0], [0]]) == 4
assert shortest_visit_all([[1], [0,2], [1]]) == 2
assert shortest_visit_all([[]]) == 0
assert shortest_visit_all([[], []]) == -1

Work and storage: O((V+E)2^V) time and O(V2^V) state storage; commonly O(V²2^V) for dense graphs. The linked problem limits V to 12. A single integer mask does not remove exponential growth.

When to recognize it: State is current node plus the set already visited. Put every possible starting state into one BFS.

Check before applying it: Do not forbid revisiting a vertex. On a star, you must revisit the center to reach all leaves.

Seed only the fixed start and forbid transitions to already-set bits. Masks then strictly grow, so a subset-DP evaluation order is available. The star may become impossible rather than merely requiring a longer walk.