Practice/Google/Leetcode 847. Shortest Path Visiting All Nodes

Leetcode 847. Shortest Path Visiting All Nodes

CodingMust

Problem

You are given an undirected connected graph represented as an adjacency list. The graph has n nodes labeled from 0 to n-1, where graph[i] contains a list of all nodes that node i is connected to.

Your task is to find the minimum number of edges you must traverse to visit every node at least once. You can start at any node, revisit nodes multiple times, and traverse the same edge multiple times.

Return the length of the shortest path that visits all nodes.

Requirements

1. Find the minimum number of edge traversals needed to visit every node
2. You may start from any node in the graph
3. Nodes and edges can be revisited as many times as needed
4. The graph is connected and undirected

Constraints

• 1 <= n <= 12 (where n is the number of nodes)
• 0 <= graph[i].length < n
• The graph is connected
• graph[i] does not contain duplicate edges
• If j is in graph[i], then i is in graph[j] (undirected property)
• Time complexity target: O(n · 2^n)
• Space complexity target: O(n · 2^n)

Examples

Example 1:

Input: graph = [[1,2],[0,2],[0,1]] Output: 2 Explanation: One optimal path is 0 -> 1 -> 2, which visits all 3 nodes in 2 steps.

Example 2:

Input: graph = [[1],[0,2],[1,3],[2]] Output: 3 Explanation: The graph forms a linear chain: 0-1-2-3. Starting from node 0: 0 -> 1 -> 2 -> 3 visits all nodes in 3 steps.

Example 3:

Input: graph = [[1,2,3],[0],[0],[0]] Output: 3 Explanation: Starting at node 1 (or any leaf), one path is: 1 -> 0 -> 2 -> 3 (3 steps). Starting at the center (node 0): 0 -> 1 -> 0 -> 2 -> 3 (4 steps). The minimum is 3 steps.