Leetcode Problem 847. Shortest Path Visiting All Nodes

847. Shortest Path Visiting All Nodes

Leetcode Solutions

If the graph has only one node, return 0.
Initialize variables: n (number of nodes), endingMask (bitmask with all nodes visited), seen (to prevent revisiting states), and queue (for BFS).
Populate queue and seen with base cases: starting at each node with the mask set to having only visited that node.
Perform BFS: a. Initialize nextQueue for the next step. b. Loop through the current queue, for each state (node, mask) loop through graph[node]. c. For each neighbor, create a new state (neighbor, nextMask) where nextMask = mask | (1 << neighbor). d. If nextMask == endingMask, return 1 + steps as all nodes have been visited. e. If the new state has not been visited, add it to nextQueue and seen. f. Increment steps and replace queue with nextQueue.
Return the number of steps once endingMask is encountered.

Programming Language

Purpose:

General Question

Debug My Code

image/screenshot of info(optional)

Full Screen