Shortest Cycle in a Graph

Shortest Cycle in a Graph

What is this problem about?

The Shortest Cycle in a Graph interview question gives you an undirected graph with n nodes and a list of edges. Find the length of the shortest cycle in the graph. If no cycle exists, return -1. The shortest cycle is also called the "girth" of the graph. This is a BFS-based graph problem where you run BFS from each node to detect the shortest cycle passing through it.

Why is this asked in interviews?

Meta and Zomato ask this HARD graph problem because finding the girth of a graph has applications in network topology analysis, circuit design, and social network clustering. The naive approach tries all pairs, but the efficient solution runs BFS from each node to find the shortest cycle through it — O(n × (n + m)) overall. It tests deep BFS understanding and the ability to detect cycles by tracking distances.

Algorithmic pattern used

The pattern is BFS from each node to find the shortest back edge. For each source node s, run BFS and track distances dist[v] from s. When you encounter an edge (u, v) where v is already visited and v != parent[u] (avoiding trivial back-edges in undirected graphs), the cycle length is dist[u] + dist[v] + 1. Take the minimum across all such back edges and all source nodes. If no back edge is ever found, return -1.

Example explanation

Graph: 0-1, 1-2, 2-3, 3-0, 0-2 (pentagon with diagonal).

BFS from node 0:

• dist[0]=0. Explore neighbors 1,3,2.
• dist[1]=1, dist[3]=1, dist[2]=1.
• From node 1: neighbor 2 already visited (dist[2]=1), not parent of 1 → cycle: dist[1]+dist[2]+1 = 1+1+1 = 3.

Shortest cycle: 3 (triangle 0-1-2-0).

Common mistakes candidates make

• Not tracking the parent node during BFS — without parent tracking, every edge in an undirected graph looks like a cycle.
• Counting cycle length as dist[u] + dist[v] instead of dist[u] + dist[v] + 1 — the +1 accounts for the edge (u,v) itself.
• Using DFS instead of BFS — DFS finds a cycle but not necessarily the shortest one.
• Not running BFS from every node — the shortest cycle might only be discoverable from a specific source.

Interview preparation tip

For the Shortest Cycle in a Graph coding problem, the BFS graph interview pattern for cycle detection and length measurement is the key. Run BFS from each node and detect back edges — the minimum dist[u] + dist[v] + 1 across all back edges gives the girth. Meta interviewers ask about the time complexity — O(n × (n + m)) in the worst case. Practice this "BFS to measure cycle length" pattern alongside the standard cycle detection algorithms. It's particularly valuable in competitive programming and graph theory interview rounds.