Shortest Cycle in a Graph — Hard Problem & Solution

Problem statement

An undirected graph has n vertices labelled 0 to n - 1 and the edges in edges, each [ui, vi]. There is at most one edge between any pair of vertices and no edge from a vertex to itself.

A cycle is a path that starts and ends at the same vertex and uses each edge at most once (and repeats no vertex other than the start). Return the length (number of edges) of the shortest cycle in the graph, or -1 if the graph has no cycle.

Example 1

Input: n = 6, edges = [[0,1],[1,2],[2,3],[3,0],[3,4],[4,5],[5,3]]
Output: 3
Explanation: The square 0-1-2-3 has length 4, the triangle 3-4-5 has length 3.

Example 2

Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4],[4,0]]
Output: 5

Example 3

Input: n = 4, edges = [[0,1],[1,2],[1,3]]
Output: -1
Explanation: The graph is a tree.

Constraints

• 2 <= n <= 1000
• 1 <= edges.length <= 1000
• edges[i].length == 2
• 0 <= ui, vi < n
• ui != vi
• there are no repeated edges

How to solve Shortest Cycle in a Graph

BFS from every vertex. During a BFS from s, any edge (u, v) that is not the tree edge into u closes a walk of length dist[u] + dist[v] + 1; the smallest such value over all starts is the girth.

Approach

1. Build adjacency lists.
2. For each start s, BFS recording dist and the BFS parent of every vertex.
3. When scanning u's neighbour v: if v is unvisited, set its distance and parent; otherwise, if v is not u's parent, update the answer with dist[u] + dist[v] + 1.
4. Return the answer, or -1 if it was never updated.

Why it works

Each candidate is the length of a closed walk built from two BFS-tree paths and one extra edge; such a walk always contains a simple cycle of at most that length, so no candidate is below the true shortest cycle. Conversely, if s lies on a shortest cycle C of length L, BFS from s reaches the vertices of C along C itself (a shorter route would create a shorter cycle), and the edge of C opposite s produces a candidate equal to L. So the minimum over all starts is exact.

Complexity

• Time — O(n · (n + m))
• Space — O(n + m)

Pitfalls

• Ignore only the edge back to u's BFS parent; any other visited neighbour gives a candidate.
• A single BFS from one vertex is not enough — it can overestimate cycles that do not pass through it.
• The graph may be disconnected; every vertex must be tried as a start.

Reference solution

Python

from typing import List
from collections import deque

def findShortestCycle(n: int, edges: List[List[int]]) -> int:
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    INF = 10 ** 9
    best = INF
    for s in range(n):
        dist = [-1] * n
        par = [-1] * n
        dist[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if dist[v] < 0:
                    dist[v] = dist[u] + 1
                    par[v] = u
                    q.append(v)
                elif par[u] != v:
                    best = min(best, dist[u] + dist[v] + 1)
    return -1 if best == INF else best

JavaScript

var findShortestCycle = function(n, edges) {
    var adj = [];
    for (var i = 0; i < n; i++) adj.push([]);
    for (var e = 0; e < edges.length; e++) {
        adj[edges[e][0]].push(edges[e][1]);
        adj[edges[e][1]].push(edges[e][0]);
    }
    var INF = 1000000000, best = INF;
    for (var s = 0; s < n; s++) {
        var dist = [], par = [];
        for (var k = 0; k < n; k++) { dist.push(-1); par.push(-1); }
        dist[s] = 0;
        var queue = [s];
        for (var h = 0; h < queue.length; h++) {
            var u = queue[h];
            for (var j = 0; j < adj[u].length; j++) {
                var v = adj[u][j];
                if (dist[v] < 0) { dist[v] = dist[u] + 1; par[v] = u; queue.push(v); }
                else if (par[u] !== v && dist[u] + dist[v] + 1 < best) best = dist[u] + dist[v] + 1;
            }
        }
    }
    return best === INF ? -1 : best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More breadth-first search problems

• Minimum Cost to Make at Least One Valid Path in a Grid Hard
• Remove Max Number of Edges to Keep Graph Fully Traversable Hard
• Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree Hard
• Minimize Malware Spread Hard
• Sum of Distances in Tree Hard
• Divide Nodes Into the Maximum Number of Groups Hard