Leetcode 847. Shortest Path Visiting All Nodes

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.

Hint 1: State Space Think about what defines a "state" in this problem. It's not just which node you're currently at—you also need to track which nodes have been visited so far. How can you efficiently represent a set of visited nodes when n ≤ 12?

Hint 2: Bitmask Representation Use a bitmask to represent which nodes have been visited. For n nodes, a bitmask of length n can represent all 2^n possible subsets of visited nodes. The goal state is when all bits are set (meaning all nodes visited).

Hint 3: BFS Approach Use BFS to explore all possible states. Each state is a tuple of (current_node, visited_bitmask). Start by adding all nodes to the queue (since you can start anywhere), each with only itself marked as visited. The first state that reaches the "all visited" bitmask is your answer.

Full Solution `` Explanation:

The key insight is that this is a shortest path problem in an augmented state space. Each state consists of:

• The current node you're at
• A bitmask representing which nodes have been visited so far

We use BFS because it naturally finds the shortest path in an unweighted graph (where each edge has cost 1).

Algorithm:

1. Initialize BFS with all possible starting nodes (n starting states), each with only that node marked as visited in the bitmask
2. For each state, explore all neighboring nodes
3. When moving to a neighbor, update the bitmask to mark that neighbor as visited
4. Track visited (node, mask) pairs to avoid redundant exploration
5. The first time we reach a state where all nodes are visited (mask has all bits set), return the step count

Time Complexity: O(n · 2^n)

• There are n nodes and 2^n possible bitmasks, giving n · 2^n possible states
• Each state is visited at most once
• Processing each state involves checking neighbors (O(n) in worst case)

Space Complexity: O(n · 2^n)

• The visited set stores up to n · 2^n states
• The queue can also grow to this size in the worst case

This approach efficiently handles the constraint that n ≤ 12, as 12 · 2^12 ≈ 49,000 states is computationally manageable.