Abstract / Summary

Find the length of the shortest cycle in an undirected graph with at least three nodes.

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 40% (80k+ submissions).

Typical patterns to solve this problem:

• Breadth First Search
• Graph

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 implementation computes the length of the shortest simple cycle in an undirected graph defined by n vertices and a list of edges. It iterates over every vertex as a potential start point, performs a breadth-first search (BFS) limited by the best cycle length found so far, and updates a global result whenever a back-edge that closes a cycle is discovered. If no cycle exists the function returns -1.

Graph construction

The first phase transforms the edge list into an adjacency representation that allows constant-time neighbor lookup.

vertices = defaultdict(list)
for u, v in edges:
    vertices[u].append(v)
    vertices[v].append(u)

The use of defaultdict(list) eliminates the need for explicit existence checks when appending neighbours, keeping the code concise and avoiding extra conditional branches.

Outer loop over start vertices

Each vertex is treated as the origin of a BFS. The loop runs from 0 to n-1.

for start in range(n):
    steps = 0
    seen  = { start: 0 }
    todo  = set([ start ])

seen records the distance from the current start vertex to every visited node. Initialising steps to 0 and todo to a set containing only the start vertex prepares the BFS frontier.

BFS frontier expansion

The BFS proceeds while there are vertices to explore and the current depth (steps) is less than the best cycle length already discovered (result). This early-stop condition prevents unnecessary work once a shorter cycle cannot be found from the current start.

while todo and steps < result:
    next = set()
    for t in todo:
        for v in vertices[t]:
            if v in seen:
                if seen[v] >= seen[t]:
                    result = min(result, seen[v] + seen[t] + 1)
            else:
                seen[v] = steps + 1
                next.add(v)
    todo   = next
    steps += 1

The inner loop iterates over each vertex t in the current frontier and examines its neighbours v.

When a neighbour has already been visited (v in seen) the code checks seen[v] >= seen[t]. This condition guarantees that the edge (t, v) connects two vertices that were discovered at the same BFS level or deeper, which corresponds to a back-edge that closes a cycle without revisiting the parent edge. The length of that cycle is computed as the sum of the distances from the start to t and to v, plus the connecting edge, and result is updated with the minimum.

If the neighbour is unseen, its distance is recorded as steps + 1 and it is added to the next frontier set. Using a set for next ensures that each vertex appears at most once in the next level, avoiding duplicate work.

Cycle detection logic

The critical test if seen[v] >= seen[t] filters out the trivial case where the edge leads back to the immediate predecessor in the BFS tree. By requiring the previously seen distance to be not smaller than the current node’s distance, the algorithm only counts cycles that involve at least three distinct vertices: the start, t, and v. The comment block in the source clarifies this reasoning, describing the three known nodes and the formula used to compute the cycle length.

Result handling

After all start vertices have been processed, the function returns the best cycle length found, or -1 if no cycle was detected.

return result if result != +inf else -1

The sentinel value +inf (imported from math) distinguishes between the “no cycle” state and any legitimate finite length.

Edge cases covered

• Graph with no edges - The adjacency list remains empty; the BFS frontier never expands, result stays at +inf, and the function returns -1.
• Disconnected components - Each component is examined independently because the outer loop iterates over every vertex. A cycle in any component can be discovered, while isolated vertices simply produce no updates.
• Single vertex - With n == 1 the outer loop runs once, but the inner BFS has no neighbours to explore, leading to a -1 return.
• Multiple parallel edges - If the input contains duplicate edges, the adjacency list will hold duplicate neighbours. The v in seen check still works because the first encounter marks the vertex, and subsequent parallel edges will be treated as back-edges, correctly reporting a cycle of length 2 (the two parallel edges) if such a configuration is allowed by the problem definition.
• Self-loops - A self-loop (u, u) would be added twice to vertices[u]. When processing u, the neighbour v equals t, and seen[v] equals seen[t]. The condition seen[v] >= seen[t] holds, and the computed cycle length becomes seen[t] + seen[t] + 1, which evaluates to 1. This correctly captures a cycle of length 1 if self-loops are considered valid cycles.

Performance optimizations observed

The algorithm incorporates several techniques that reduce unnecessary computation:

• Early termination of BFS levels - The loop condition steps < result stops the search once the current depth cannot improve the best cycle length, pruning large portions of the search space in dense graphs where a short cycle is found early.
• Set-based frontier - Using a set for todo and next eliminates duplicate entries without extra bookkeeping, ensuring each vertex is processed at most once per BFS level.
• Distance dictionary (seen) - Storing distances in a hash map provides O(1) lookup for the v in seen test and for retrieving the distance values needed to compute cycle lengths.
• Minimal state per start vertex - The BFS reinitialises seen and todo for each start, avoiding the overhead of clearing large structures between iterations.
• Avoidance of explicit parent tracking - The condition seen[v] >= seen[t] implicitly prevents counting the edge that leads back to the parent node, removing the need for an additional parent array.

Together, these choices keep the per-start BFS work proportional to the number of edges explored up to the current best cycle length, making the overall execution efficient for moderate-size graphs.

Imagine you have a bunch of dots on a piece of paper, and you draw lines between some of them to connect them together. This code is like a curious explorer looking for the smallest circle you can make by following those lines.

First, the code creates a map so it knows exactly which dots are connected to each other. It wants to find the shortest loop, so it starts at every single dot and begins a journey. It keeps track of how many steps it takes to reach each new dot and writes down that number.

When the explorer stands on one dot and sees another dot that has already been visited, it means there is a hidden path that creates a loop. Because the explorer already knows how many steps it took to get to both of those dots, it uses the math of those steps to figure out the size of the circle they just found. It keeps a record of the very smallest circle it discovers during its travels. If it finishes looking at every dot and never finds a circle, it simply says that none exist.

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

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

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	Go	Python	TS
	Progiez	C++		Java		Python
github	charles-wangkai			Java
	everthis		JS
	fsq	C++
	muhammadfarhankt				Go
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
muhammadfarhankt	Go
wisdompeak	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