Solution: Shortest Path Visiting All Nodes

Statement

You are given an undirected connected graph with n nodes numbered from $0$ to $n-1$. The graph is provided as an adjacency list, graph, where graph[i] contains all nodes that share an edge with node i.

Your task is to find the length of the shortest path that visits every node. You may:

• Start from any node.

• End at any node.

• Revisit nodes and reuse edges as many times as needed.

Constraints:

• n $==$ graph.length

• $1 \leq$ n $\leq 12$

• $0 \leq$ graph[i].length $<$ n

• graph[i] does not contain i.

• If graph[a] contains b, then graph[b] contains a.

• The input graph is always connected.

Solution

The problem asks for the minimum number of steps needed to visit every node in an undirected, connected graph. A naive approach might attempt to explore all possible paths or rely on depth-first search (DFS). However, DFS explores one path deeply before considering alternatives. This implies that it may eventually find a solution, but has no mechanism for guaranteeing that the solution is the shortest without exploring all other possibilities as well. The number of potential paths grows factorially, making direct enumeration computationally inefficient, even for graphs of size $12$.

Because all edges have equal cost (each move takes exactly one step), breadth-first search (BFS) is the natural choice. BFS explores the graph level by level: first all states reachable in $1$ step, then all states reachable in $2$ steps, and so on. This structure guarantees that the first time BFS encounters a state where all nodes have been visited, that state corresponds to the minimum number of steps. This property makes BFS superior to DFS and any brute-force enumeration for this problem.

To use BFS effectively, the algorithm must define what constitutes a state. Tracking only the current node is insufficient because that tells us nothing about which nodes remain unvisited. Tracking only the visited set is also insufficient, because we would not know our current position to continue exploring. Therefore, the algorithm uses state compressionIn graph traversals, state compression refers to techniques used to reduce the memory required to store the graph's structure or the traversal's state information, especially for extremely large graphs., representing each state as a pair:

1. The current node

2. The visited set (encoded efficiently as a bitmask)

This combination uniquely describes the algorithm’s progress at any moment.

About the bitmask:

A bitmask is simply an integer interpreted in binary form, where the $n$ bits correspond to the $n$ nodes of the graph.

• It is an ...