#847
Shortest Path Visiting All Nodes
expert · 1065 · lc hard +32 · verified · 65.8% accepted · 4,617 likes · top 71%
Description
You have an undirected, connected graph of n nodes labeled 0 through n - 1, described by graph where graph[i] lists all nodes directly connected to node i.
Return the length of the shortest path that visits every node. You may begin and end at any node, revisit nodes, and reuse edges.
Example 1:
Input: graph = [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]
Example 2:
Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]
Code
1
2
3