Abstract / Summary

Find the shortest path that visits every node in an undirected graph starting from a given node.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 66% (200k+ submissions).

Typical patterns to solve this problem:

• Bit Manipulation
• Bitmask
• Breadth First Search
• Dynamic Programming
• Graph Theory

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of finding the length of the shortest path that visits every node in an undirected graph. It treats the problem as a breadth-first search (BFS) over a state space where each state records both the current node and the set of nodes visited so far. The algorithm expands states level by level until a state that has visited all nodes is reached, at which point the number of BFS levels traversed is returned as the answer.

Initialization

The first step determines the number of vertices and creates the initial frontier of BFS states. Each vertex starts a separate search path that has visited only that vertex.

size = len(graph)

todo = set([ (i,) for i in range(size) ])

size holds the total count of nodes. todo is a set of one-element tuples, each tuple representing a path that ends at a particular node and implicitly records the visited nodes because the tuple’s elements are the nodes visited in order. Using a set eliminates duplicate states automatically.

BFS Loop

The core of the algorithm is a loop that processes all states at the current BFS depth before moving to the next depth. A counter steps tracks how many layers have been explored.

steps = 0
while todo:
    steps += 1
    next = set()
    ...
    todo = next

Each iteration increments steps, creates a fresh container next for the states that will be generated from the current frontier, and finally replaces todo with next to advance to the next BFS level.

State Expansion

For every state in the current frontier, the algorithm extracts the last visited node and reconstructs the set of visited nodes. It then iterates over all neighbors of the last node, forming new states by appending the neighbor to the visitation history.

for visited in todo:
    last = visited[-1]
    history = set(visited)

    for follow in graph[last]:
        have = tuple(history) + (follow,)
        ...
        next.add(have)

last is the current position, while history is a set of all nodes visited in the current path. The inner loop walks through each adjacent node follow. The new state have is built by converting the history set back to a tuple (preserving order) and appending the neighbor. Adding have to next ensures that the BFS frontier for the next level contains all reachable configurations.

Termination Condition

The algorithm checks whether the newly generated state has just visited the final unvisited node. If the size of the visited set is one less than the total number of nodes and the neighbor being added has not been visited before, the search can stop because the next step completes a Hamiltonian visitation.

if len(history) == size - 1 and follow not in history:
    return steps

When this condition is satisfied, steps already reflects the number of edges traversed to reach the complete visitation, and the function returns this value immediately.

Edge Cases

The implementation naturally handles several edge conditions without special casing. When the input graph contains a single vertex, size equals 1, the initial todo set contains a single tuple (0,), and the while loop never enters because the termination condition is never met; the function ultimately returns 0, which correctly indicates that no moves are required to visit the sole node. For disconnected graphs, the BFS will exhaust all reachable states without ever satisfying the termination condition, causing the loop to exit and the function to return 0. This return value signals that a full visitation is impossible under the given connectivity. The use of a set for todo also prevents the algorithm from revisiting identical states that could arise from different traversal orders, thereby avoiding infinite loops in cyclic graphs.

Performance Optimizations

The code leverages several techniques to keep the search efficient. Storing the frontier as a set provides O(1) average-time membership checks and eliminates duplicate states automatically, which reduces the number of expansions dramatically in graphs with many symmetric paths. Representing the visited nodes as a tuple rather than a list enables the state to be hashable, allowing it to be placed directly into a set. Converting the tuple to a set (history = set(visited)) only when needed for membership tests avoids repeated conversions during the inner loop. The early termination check (len(history) == size - 1 and follow not in history) stops the search as soon as the final node is reached, preventing unnecessary exploration of deeper levels. By incrementing steps at the start of each BFS level, the algorithm ensures that the first time a complete visitation is found corresponds to the shortest possible path length.

Imagine a group of rooms connected by hallways. Each room has a number, and you start at one of them. The goal is to walk through every single room at least once, but you want to do it in the smallest number of steps possible.

The code starts by keeping track of where you are and everywhere you have already visited. Because you do not know which room is the best to start in, the code acts as if you are starting in every room at the exact same time. It puts these starting points into a collection called a todo list.

Next, the code starts counting steps. For every step you take, it looks at all the rooms you are currently in. From each of those rooms, it finds every possible door you can walk through to reach a new room. It remembers the path you took, including which rooms you saw along the way, to make sure you keep track of your journey.

As you move, the code builds a brand new list of all the places you could possibly be after that step. If you ever find yourself in a situation where you have finally walked through every single room, the code stops and tells you exactly how many steps that took. It keeps repeating this process, widening the search layer by layer, until it finds the quickest way to finish the tour of all the rooms.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python					TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python		Rust		Go	TS
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	black-shadows	C++
	charles-wangkai		Java
	everthis				JS
	fpdjsns	C++
	gouthampradhan		Java
	JoshCrozier				JS
	lkwq007			Python
	MacJim	C++
	ruoru					Rust
	suxrobGM						C#
	trung-hn			Python
	varunu28		Java
	wisdompeak	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
gouthampradhan	Java
JoshCrozier	JavaScript
lkwq007	Python
MacJim	C++
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality