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 ...