Shortest Cycle in a Graph - Solution & Explanation
Problem Statement
There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1. The edges in the graph are represented by a given 2D integer array edges, where edges[i] = [ui, vi] denotes an edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.
Return the length of the shortest cycle in the graph. If no cycle exists, return -1.
A cycle is a path that starts and ends at the same node, and each edge in the path is used only once.
Example 1:
Input: n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]] Output: 3 Explanation: The cycle with the smallest length is : 0 -> 1 -> 2 -> 0
Example 2:
Input: n = 4, edges = [[0,1],[0,2]] Output: -1 Explanation: There are no cycles in this graph.
Constraints:
2 <= n <= 10001 <= edges.length <= 1000edges[i].length == 20 <= ui, vi < nui != vi- There are no repeated edges.
Approach Overview
Problem Overview: Given an undirected graph with n nodes and a list of edges, return the length of the shortest cycle. If no cycle exists, return -1. The key challenge is identifying the minimum cycle length among all possible cycles in the graph.
Approach 1: BFS from Every Node to Detect the Shortest Cycle (Time: O(V * (V + E)), Space: O(V + E))
This approach runs Breadth-First Search starting from every node. While performing BFS, maintain a distance array and track the parent of each node. If you encounter a neighbor that has already been visited and is not the parent of the current node, a cycle is found. The cycle length equals distance[current] + distance[neighbor] + 1. BFS explores nodes level by level, which naturally helps detect the shortest cycle passing through the starting node. Repeat this process for every vertex and keep the minimum cycle length found.
This method works well because BFS guarantees the shortest path discovery in an unweighted graph. When a cross-edge appears during traversal, it forms the smallest possible cycle involving those nodes. The adjacency list representation keeps traversal efficient even for dense graphs.
Approach 2: Graph Coloring with DFS Cycle Detection (Time: O(V + E), Space: O(V))
This method uses Depth-First Search with graph coloring to detect cycles. Each node is marked as unvisited, visiting, or visited. While exploring neighbors recursively, encountering a node currently in the recursion stack indicates a cycle. By storing the depth (or discovery time) of nodes, you can compute the cycle length when a back edge is detected. Continue scanning all components to track the minimum cycle encountered.
DFS works well for general graph cycle detection and runs in linear time relative to nodes and edges. However, DFS does not naturally guarantee the globally shortest cycle because traversal order can influence which cycles appear first. Additional bookkeeping is required to compute cycle lengths accurately.
Recommended for interviews: The BFS-from-every-node approach is usually expected. It clearly demonstrates understanding of shortest-path traversal in unweighted graphs and reliably finds the minimum cycle length. Mentioning DFS cycle detection is useful to show knowledge of alternative graph techniques, but BFS provides the most straightforward and correct solution for shortest cycle problems.
Approach 1: BFS to Detect Shortest Cycle
Breadth-first search (BFS) is an effective method for traversing graphs level by level. By initiating a BFS traversal from each unvisited node, it's possible to detect the shortest cycle in an undirected graph. During the traversal, we maintain parent-child relationships to avoid revisiting the immediate parent node and ensure that cycles are accurately identified.
This Python solution leverages BFS to detect the shortest cycle. Each node in the graph is used as a starting point, and BFS is executed to find any cycles that involve returning to the starting node. The queue maintains the current node, the parent node, and the cumulative distance from the start. If a previously visited node is encountered that isn't the parent, a cycle is detected.
Code
Python
Java
C++
C
JavaScript
Complexity
Time Complexity: O(n * m), where n is the number of vertices and m is the number of edges, as each edge and node is processed in the BFS.
Space Complexity: O(n + m), due to graph representation and BFS queue/visited set.
Approach 2: Graph Coloring using DFS to Detect Cycles
Graph coloring is a technique used to detect cycles in various graph algorithms. By employing a three-color method (white, gray, black), DFS can be utilized to identify cycles, especially in directed graphs when an already 'gray' node is encountered. For undirected graphs, proper tracking of predecessors ensures valid cycle detection.
This Python solution applies DFS and graph coloring to detect cycles. 'G' indicates nodes currently being explored, 'W' for unvisited, and 'B' for completed nodes. It ensures cycles are detected by revisiting already 'gray' nodes.
Code
Python
Java
C++
C#
JavaScript
Complexity
Time Complexity: O(n + m) due to DFS exploration.
Space Complexity: O(n), with color array and recursion depth.
Approach 3: Enumerate edges + BFS
We first construct the adjacency list g of the graph according to the array edges, where g[u] represents all the adjacent vertices of vertex u.
Then we enumerate the two-directional edge (u, v), if the path from vertex u to vertex v still exists after deleting this edge, then the length of the shortest cycle containing this edge is dist[v] + 1, where dist[v] represents the shortest path length from vertex u to vertex v. We take the minimum of all these cycles.
The time complexity is O(m^2) and the space complexity is O(m + n), where m and n are the length of the array edges and the number of vertices.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Enumerate points + BFS
Similar to Solution 1, we first construct the adjacency list g of the graph according to the array edges, where g[u] represents all the adjacent vertices of vertex u.
Then we enumerate the vertex u, if there are two paths from vertex u to vertex v, then we currently find a cycle, the length is the sum of the length of the two paths. We take the minimum of all these cycles.
The time complexity is O(m times n) and the space complexity is O(m + n), where m and n are the length of the array edges and the number of vertices.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| BFS to Detect Shortest Cycle | Time Complexity: O(n * m), where n is the number of vertices and m is the number of edges, as each edge and node is processed in the BFS. |
| Graph Coloring using DFS to Detect Cycles | Time Complexity: O(n + m) due to DFS exploration. |
| Enumerate edges + BFS | — |
| Enumerate points + BFS | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS from Every Node | O(V * (V + E)) | O(V + E) | Best approach for finding the exact shortest cycle in an unweighted graph |
| DFS Graph Coloring | O(V + E) | O(V) | Useful for general cycle detection and understanding graph traversal patterns |
Video Solution
Shortest Cycle in a Graph | Biweekly Contest 101 • codingMohan • 5,541 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Shortest Cycle in a Graph easy or hard?
Shortest Cycle in a Graph Python/Java solution
How to solve Shortest Cycle in a Graph in O(n)?
What is the best approach for Shortest Cycle in a Graph?
Is Shortest Cycle in a Graph asked at Google/Amazon/Meta?
What data structure is used in Shortest Cycle in a Graph?
What is the time complexity of Shortest Cycle in a Graph?
Ready to solve this problem?
Practice Shortest Cycle in a Graph with our built-in code editor and test cases.
Practice on FleetCode