Is Shortest Cycle in a Graph easy or hard?

Shortest Cycle in a Graph is considered a hard problem because it combines graph traversal with careful cycle detection and distance tracking. Implementing BFS correctly with parent tracking is essential to avoid false cycle detection. The challenge lies in ensuring the smallest cycle across the entire graph is returned.

Shortest Cycle in a Graph Python/Java solution

The standard implementation builds an adjacency list and performs BFS from each node. During traversal, maintain a distance array and parent reference. When a visited neighbor that is not the parent is encountered, compute the cycle length and update the minimum. The same algorithm works consistently across Python, Java, C++, and JavaScript.

How to solve Shortest Cycle in a Graph in O(n)?

Cycle detection itself can be done in O(V + E) using DFS with graph coloring or recursion stack tracking. However, guaranteeing the globally shortest cycle generally requires running BFS from each node, leading to O(V * (V + E)). Linear time solutions typically detect cycles but do not always ensure the minimum cycle length.

What is the best approach for Shortest Cycle in a Graph?

Running Breadth-First Search (BFS) from every node is the most reliable method. BFS explores the graph level by level, and when it encounters a previously visited node that is not the parent, a cycle is detected. This allows direct computation of the cycle length. Repeating BFS from each vertex guarantees the minimum cycle is found.

Is Shortest Cycle in a Graph asked at Google/Amazon/Meta?

Graph traversal and cycle detection problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of shortest cycle detection test understanding of BFS, graph representation, and parent tracking. Problems like this are common in advanced graph interview rounds.

What data structure is used in Shortest Cycle in a Graph?

The graph is usually stored as an adjacency list for efficient traversal. BFS uses a queue along with distance and parent arrays to track levels and avoid revisiting nodes incorrectly. DFS-based approaches rely on recursion stacks or color arrays to identify cycles.

What is the time complexity of Shortest Cycle in a Graph?

The typical BFS-based solution runs in O(V * (V + E)) time where V is the number of vertices and E is the number of edges. BFS is executed once for every node, and each traversal processes all edges and vertices in the worst case. Space complexity is O(V + E) for the adjacency list and BFS data structures.

Description Hints 2 Solution Video 10:07

2608. Shortest Cycle in a Graph

Hard40.5% acceptance4 companies

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] = [u_i, v_i] denotes an edge between vertex u_i and vertex v_i. 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 <= 1000
1 <= edges.length <= 1000
edges[i].length == 2
0 <= u_i, v_i < n
u_i != v_i
There are no repeated edges.

Asked at 4 companies

Zomato PhonePe

Google Meta

Topics

Breadth-First Search Graph

Hints open one at a time

Hint 1

How can BFS be used?

Hint 2

For each vertex u, calculate the length of the shortest cycle that contains vertex u using BFS

10:07

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution