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.
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.
Python
Java
C++
C
JavaScript
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.
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.
Python
Java
C++
C#
JavaScript
Time Complexity: O(n + m) due to DFS exploration.
Space Complexity: O(n), with color array and recursion depth.
| 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. |
| 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 |
Shortest Cycle in a Graph | Biweekly Contest 101 • codingMohan • 5,333 views views
Watch 9 more video solutions →Practice Shortest Cycle in a Graph with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor