Leetcode Problem 847. Shortest Path Visiting All Nodes

847. Shortest Path Visiting All Nodes

Leetcode Solutions

Breadth-First Search (BFS)

  1. If the graph has only one node, return 0.
  2. Initialize variables: n (number of nodes), endingMask (bitmask with all nodes visited), seen (to prevent revisiting states), and queue (for BFS).
  3. Populate queue and seen with base cases: starting at each node with the mask set to having only visited that node.
  4. 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.
  5. Return the number of steps once endingMask is encountered.
UML Thumbnail

DFS + Memoization (Top-Down DP)

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...