hardGraphsPure DSA~45 min
Shortest Walk Visiting Every Datacenter
A maintenance bot must visit every datacenter at least once, starting from any one, and may revisit datacenters and reuse links freely. Find the length of the shortest walk that covers all of them.
Problem
Given an undirected connected graph of n nodes as an adjacency list graph (graph[i] lists neighbours of i), return the length of the shortest path that visits every node. You may start and end at any node and revisit nodes and edges.
Input
An adjacency list graph of n nodes (0-indexed).
Output
The minimum number of edges in a walk covering all nodes.
Constraints
- 1 ≤ n ≤ 12
- 0 ≤ graph[i].length < n
- The graph is connected and undirected.
Examples
Example 1
Input
[[1,2,3],[0],[0],[0]]
Output
4
Star graph: e.g. 1→0→2→0→3 uses 4 edges to cover all nodes.
Example 2
Input
[[1],[0,2,4],[1,3],[2],[1,5],[4]]
Output
5
A path-like graph traversed once end to end covers all 6 nodes in 5 edges.