Watch 10 video solutions for Shortest Cycle in a Graph, a hard level problem involving Breadth-First Search, Graph. This walkthrough by codingMohan has 5,333 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 != viProblem 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 | 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 |