LeetCode 2608 - Shortest Cycle in a Graph

LeetCode Problem 2608

Difficulty: 🔴 Hard
Topics: Breadth-First Search, Graph Theory

Solution

Problem Understanding

The problem gives us an undirected graph with n vertices labeled from 0 to n - 1. The graph is represented using an edge list, where each edge connects two vertices in both directions.

Our task is to find the length of the shortest cycle in the graph. A cycle is a path that starts and ends at the same vertex without reusing any edge. Since the graph is undirected, traversing an edge from u to v is the same as traversing from v to u.

The input consists of:

• An integer n, the number of vertices.
• A list edges, where each element [u, v] represents an undirected edge.

The output should be:

• The length of the shortest cycle if at least one cycle exists.
• -1 if the graph is acyclic.

The constraints are relatively small:

• n <= 1000
• edges.length <= 1000

These constraints strongly suggest that graph traversal algorithms such as Breadth-First Search (BFS) are feasible even if repeated multiple times.

Several important observations come from the problem guarantees:

• No self-loops exist, so cycles of length 1 are impossible.
• No duplicate edges exist, so cycles of length 2 are also impossible.
• The graph may be disconnected, so we must consider all connected components.
• The shortest cycle could exist entirely inside one component while others are trees.

Important edge cases include:

• A graph with no cycles at all.
• Multiple disconnected components.
• Multiple cycles with different lengths.
• Dense local structures where several cycles overlap.
• Very small graphs where a cycle cannot possibly exist.

Approaches

Brute Force Approach

A naive solution would attempt to enumerate all possible cycles in the graph and track the minimum length encountered.

One possible brute-force strategy is:

• Start a DFS from every node.
• Explore all possible paths.
• Detect when a path returns to the starting node.
• Record cycle lengths.

This approach is correct because it eventually explores every possible cycle. However, it is extremely inefficient because the number of simple paths in a graph grows exponentially. Even with pruning, the repeated exploration becomes prohibitively expensive.

For graphs with up to 1000 vertices, exhaustive cycle enumeration is not practical.

Key Insight

The important observation is that BFS naturally finds shortest paths in unweighted graphs.

Suppose we run BFS from a starting node start.

During BFS, if we encounter a previously visited neighbor that is not the parent of the current node, then we have found a cycle.

Why does this work?

• BFS explores nodes level by level.
• Therefore, the first time we reconnect through a non-parent edge, we can compute a valid cycle length using the distances already discovered.

For a cycle detected between nodes u and v:

cycle_length = dist[u] + dist[v] + 1

This works because:

• dist[u] is the shortest distance from start to u
• dist[v] is the shortest distance from start to v
• The edge (u, v) closes the cycle

By running BFS from every node, we ensure that every possible shortest cycle is considered.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(n)	Enumerates all possible cycles
Optimal BFS	O(n × (n + e))	O(n + e)	Runs BFS from every node and detects cycles efficiently

Here:

• n is the number of vertices
• e is the number of edges

Since both are at most 1000, the BFS solution is efficient enough.

Algorithm Walkthrough

Optimal BFS Algorithm

1. Build an adjacency list for the graph.

Since the graph is undirected, every edge [u, v] is added in both directions. 2. Initialize a variable shortest_cycle to infinity.

This variable keeps track of the minimum cycle length found across all BFS traversals. 3. Run BFS starting from every node.

We do this because the shortest cycle may not involve every node, and disconnected components are possible. 4. For each BFS traversal, maintain:

• A distance array initialized to -1
• A parent array initialized to -1
• A queue for BFS

The distance array stores shortest distances from the starting node.

The parent array prevents falsely detecting the immediate reverse edge as a cycle. 5. Start BFS from the current source node.

Set:

distance[start] = 0

Then push the node into the queue. 6. Process nodes level by level.

For each current node u, examine every neighbor v. 7. If v has not been visited yet:

• Set its distance
• Record its parent
• Push it into the queue

8. Otherwise, if v is already visited and v is not the parent of u:

We found a cycle.

Compute:

cycle_length = distance[u] + distance[v] + 1

Then update the global minimum. 9. After all BFS traversals finish:

• Return the minimum cycle length found
• If no cycle was discovered, return -1

Why it works

BFS guarantees shortest path distances in unweighted graphs. When BFS encounters an already visited node that is not the parent, the current edge closes a cycle.

The computed cycle length correctly represents the number of edges in that cycle because:

• One shortest path connects the source to u
• Another shortest path connects the source to v
• The edge (u, v) completes the loop

Running BFS from every node guarantees that the globally shortest cycle is eventually discovered.

Python Solution

from collections import deque
from typing import List

class Solution:
    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:
        graph = [[] for _ in range(n)]

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        shortest_cycle = float("inf")

        for start in range(n):
            distance = [-1] * n
            parent = [-1] * n

            queue = deque([start])
            distance[start] = 0

            while queue:
                current = queue.popleft()

                for neighbor in graph[current]:
                    if distance[neighbor] == -1:
                        distance[neighbor] = distance[current] + 1
                        parent[neighbor] = current
                        queue.append(neighbor)

                    elif parent[current] != neighbor:
                        cycle_length = (
                            distance[current]
                            + distance[neighbor]
                            + 1
                        )

                        shortest_cycle = min(
                            shortest_cycle,
                            cycle_length
                        )

        return shortest_cycle if shortest_cycle != float("inf") else -1

Implementation Explanation

The first step constructs the adjacency list representation of the graph. Since the graph is undirected, each edge is inserted twice.

The outer loop runs BFS from every node. This guarantees that every possible cycle can be detected.

Inside each BFS:

• distance[node] stores the shortest number of edges from the starting node.
• parent[node] stores the node from which we first reached that node.

The parent tracking is critical. In an undirected graph, every edge appears twice. Without checking the parent relationship, the traversal would incorrectly interpret the reverse traversal edge as a cycle.

When we encounter a previously visited neighbor that is not the parent, we compute the cycle length using:

distance[current] + distance[neighbor] + 1

This formula counts:

• The shortest path from the start to current
• The shortest path from the start to neighbor
• The connecting edge between them

Finally, if no cycle was found, the answer remains infinity and we return -1.

Go Solution

package main

import "container/list"

func findShortestCycle(n int, edges [][]int) int {
	graph := make([][]int, n)

	for _, edge := range edges {
		u, v := edge[0], edge[1]
		graph[u] = append(graph[u], v)
		graph[v] = append(graph[v], u)
	}

	const INF int = 1 << 30
	shortestCycle := INF

	for start := 0; start < n; start++ {
		distance := make([]int, n)
		parent := make([]int, n)

		for i := 0; i < n; i++ {
			distance[i] = -1
			parent[i] = -1
		}

		queue := list.New()
		queue.PushBack(start)
		distance[start] = 0

		for queue.Len() > 0 {
			front := queue.Front()
			queue.Remove(front)

			current := front.Value.(int)

			for _, neighbor := range graph[current] {
				if distance[neighbor] == -1 {
					distance[neighbor] = distance[current] + 1
					parent[neighbor] = current
					queue.PushBack(neighbor)
				} else if parent[current] != neighbor {
					cycleLength := distance[current] + distance[neighbor] + 1

					if cycleLength < shortestCycle {
						shortestCycle = cycleLength
					}
				}
			}
		}
	}

	if shortestCycle == INF {
		return -1
	}

	return shortestCycle
}

Go-specific Notes

The Go solution mirrors the Python implementation closely.

A few language-specific details are worth noting:

• Go does not provide a built-in deque, so container/list is used for BFS queue operations.
• Arrays are initialized explicitly because Go does not support Python-style list multiplication.
• A large constant INF is used instead of floating-point infinity.
• Slices are used for adjacency lists because they dynamically grow as neighbors are added.

No integer overflow concerns exist because the maximum cycle length is at most n, which is only 1000.

Worked Examples

Example 1

n = 7
edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]

Graph Structure

Component 1:

0 - 1
 \ /
  2

Component 2:

3 - 4
|   |
6 - 5

BFS Starting from Node 0

Initial state:

Node	Distance	Parent
0	0	-1
1	-1	-1
2	-1	-1

Queue:

Queue
[0]

Process node 0:

• Visit 1
• Visit 2

Updated state:

Node	Distance	Parent
0	0	-1
1	1	0
2	1	0

Queue:

Queue
[1, 2]

Process node 1:

• Neighbor 0 is parent, ignore
• Neighbor 2 already visited and not parent

Cycle found:

distance[1] + distance[2] + 1
= 1 + 1 + 1
= 3

Shortest cycle becomes 3.

No smaller cycle is possible because:

• Self-loops are forbidden
• Duplicate edges are forbidden

Final answer:

3

Example 2

n = 4
edges = [[0,1],[0,2]]

Graph:

1
 \
  0
 /
2

Node 3 is isolated.

Running BFS from every node never encounters a previously visited non-parent neighbor.

Therefore, no cycle exists.

Final answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × (n + e))	BFS runs once per node
Space	O(n + e)	Adjacency list plus BFS arrays

The adjacency list requires O(n + e) space because every edge is stored twice in an undirected graph.

Each BFS traversal processes every node and edge once, giving O(n + e) per BFS. Since BFS is executed from every node, the total complexity becomes:

O(n × (n + e))

With the given constraints, this is efficient enough in practice.

Test Cases

from typing import List

class Solution:
    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:
        from collections import deque

        graph = [[] for _ in range(n)]

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        shortest_cycle = float("inf")

        for start in range(n):
            distance = [-1] * n
            parent = [-1] * n

            queue = deque([start])
            distance[start] = 0

            while queue:
                current = queue.popleft()

                for neighbor in graph[current]:
                    if distance[neighbor] == -1:
                        distance[neighbor] = distance[current] + 1
                        parent[neighbor] = current
                        queue.append(neighbor)

                    elif parent[current] != neighbor:
                        cycle_length = (
                            distance[current]
                            + distance[neighbor]
                            + 1
                        )

                        shortest_cycle = min(
                            shortest_cycle,
                            cycle_length
                        )

        return shortest_cycle if shortest_cycle != float("inf") else -1

solution = Solution()

assert solution.findShortestCycle(
    7,
    [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]
) == 3  # triangle cycle

assert solution.findShortestCycle(
    4,
    [[0,1],[0,2]]
) == -1  # acyclic graph

assert solution.findShortestCycle(
    3,
    [[0,1],[1,2],[2,0]]
) == 3  # single triangle

assert solution.findShortestCycle(
    4,
    [[0,1],[1,2],[2,3],[3,0]]
) == 4  # square cycle

assert solution.findShortestCycle(
    6,
    [[0,1],[1,2],[2,0],[2,3],[3,4],[4,2]]
) == 3  # multiple cycles

assert solution.findShortestCycle(
    5,
    [[0,1],[1,2],[2,3],[3,4]]
) == -1  # simple path

assert solution.findShortestCycle(
    1_000,
    []
) == -1  # empty graph

assert solution.findShortestCycle(
    6,
    [[0,1],[1,2],[2,3],[3,0],[0,2]]
) == 3  # smaller cycle inside larger cycle

assert solution.findShortestCycle(
    8,
    [[0,1],[1,2],[2,3],[3,0],[4,5],[5,6],[6,7],[7,4]]
) == 4  # disconnected cyclic components

Test Summary

Test	Why
Triangle graph	Smallest valid cycle
Acyclic graph	Ensures -1 is returned
Single cycle	Basic correctness
Square cycle	Non-triangle cycle
Multiple overlapping cycles	Must choose shortest
Linear chain	No cycles present
Empty edge set	Handles isolated nodes
Nested cycles	Detects minimum correctly
Multiple disconnected cycles	Works across components

Edge Cases

Graph With No Cycles

A tree or disconnected forest contains no cycles at all. This is an important edge case because naive implementations may accidentally interpret parent edges as cycles in undirected graphs.

The implementation avoids this by tracking the parent of each node during BFS. When revisiting a node, the algorithm only counts it as a cycle if the neighbor is not the parent.

If no cycle is ever found, the result remains infinity and the function correctly returns -1.

Disconnected Graphs

The graph may contain several disconnected components. Some components may contain cycles while others may not.

A buggy implementation might only run BFS from node 0 and miss cycles in other components.

This solution runs BFS starting from every node, guaranteeing that all components are explored completely.

Overlapping Cycles

Graphs may contain multiple cycles sharing edges or vertices.

For example:

0 - 1
| X |
2 - 3

Such cases are tricky because different traversal orders may discover longer cycles first.

Because BFS always computes shortest distances in unweighted graphs, every detected cycle length is valid, and taking the global minimum guarantees the shortest cycle is returned.