Shortest Path Visiting All Nodes
Hard · graph traversal
You are given an undirected, connected graph with n nodes labelled 0 to n - 1. The graph is given as adjacency lists: graph[i] holds every node that shares an edge with node i.
A walk starts at any node you like and then moves along edges one at a time. A walk may pass through the same node, and use the same edge, as many times as it wants.
Return the length of the shortest walk that visits every node at least once. The length of a walk is the number of edges it uses, counting an edge each time it is used. A graph with a single node needs a walk of length 0.
Examples
Example 1
Input: graph = [[1, 2, 3], [0], [0], [0]]
Output: 4
Node 0 is joined to three leaves. A walk such as 1, 0, 2, 0, 3 visits all four nodes in 4 edges, and nothing shorter does.
Example 2
Input: graph = [[1], [0, 2], [1, 3], [2]]
Output: 3
The nodes form a line, so walking from one end to the other, 0, 1, 2, 3, visits them all in 3 edges.
Example 3
Input: graph = [[]]
Output: 0
There is only one node, and you are already standing on it.
Constraints
- 1 <= n <= 12, where n is the number of nodes (len(graph))
- graph[i] does not contain i, and has no repeated entries
- If graph[a] contains b then graph[b] contains a
- The graph is connected