Shortest Cycle in a Graph

Problem

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 theshortest 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.

Examples

Example 1

1
2
3
4
5
6



![](https://assets.leetcode.com/uploads/2023/01/04/cropped.png)

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

1
2
3
4
5
6



![](https://assets.leetcode.com/uploads/2023/01/04/croppedagin.png)

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 <= ui, vi < n
ui != vi
There are no repeated edges.

Solution

Method 1 – BFS from Every Node

Intuition

To find the shortest cycle in an undirected graph, we can use BFS from every node. If we revisit a node (other than the parent) during BFS, we’ve found a cycle. The shortest such cycle across all BFS runs is the answer.

Approach

Build the adjacency list for the graph.
For each node, run BFS:
- Track the distance from the start node and the parent for each node.
- If you reach a neighbor that is not the parent and already visited, a cycle is found. The cycle length is the sum of distances to the two nodes plus one.
- Keep track of the minimum cycle length found.
If no cycle is found, return -1.
Otherwise, return the minimum cycle length.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution {
public:
    int findShortestCycle(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n);
        for (auto& e : edges) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        int ans = INT_MAX;
        for (int i = 0; i < n; ++i) {
            vector<int> dist(n, -1), par(n, -1);
            queue<int> q;
            dist[i] = 0;
            q.push(i);
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int v : g[u]) {
                    if (dist[v] == -1) {
                        dist[v] = dist[u] + 1;
                        par[v] = u;
                        q.push(v);
                    } else if (par[u] != v) {
                        ans = min(ans, dist[u] + dist[v] + 1);
                    }
                }
            }
        }
        return ans == INT_MAX ? -1 : ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


func findShortestCycle(n int, edges [][]int) int {
    g := make([][]int, n)
    for _, e := range edges {
        g[e[0]] = append(g[e[0]], e[1])
        g[e[1]] = append(g[e[1]], e[0])
    }
    ans := 1<<31 - 1
    for i := 0; i < n; i++ {
        dist := make([]int, n)
        for j := range dist {
            dist[j] = -1
        }
        par := make([]int, n)
        for j := range par {
            par[j] = -1
        }
        q := []int{i}
        dist[i] = 0
        for len(q) > 0 {
            u := q[0]
            q = q[1:]
            for _, v := range g[u] {
                if dist[v] == -1 {
                    dist[v] = dist[u] + 1
                    par[v] = u
                    q = append(q, v)
                } else if par[u] != v {
                    if ans > dist[u]+dist[v]+1 {
                        ans = dist[u]+dist[v]+1
                    }
                }
            }
        }
    }
    if ans == 1<<31-1 {
        return -1
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


class Solution {
    public int findShortestCycle(int n, int[][] edges) {
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; ++i) g.add(new ArrayList<>());
        for (int[] e : edges) {
            g.get(e[0]).add(e[1]);
            g.get(e[1]).add(e[0]);
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            int[] dist = new int[n];
            int[] par = new int[n];
            Arrays.fill(dist, -1);
            Arrays.fill(par, -1);
            Queue<Integer> q = new LinkedList<>();
            dist[i] = 0;
            q.offer(i);
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : g.get(u)) {
                    if (dist[v] == -1) {
                        dist[v] = dist[u] + 1;
                        par[v] = u;
                        q.offer(v);
                    } else if (par[u] != v) {
                        ans = Math.min(ans, dist[u] + dist[v] + 1);
                    }
                }
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution {
    fun findShortestCycle(n: Int, edges: Array<IntArray>): Int {
        val g = List(n) { mutableListOf<Int>() }
        for (e in edges) {
            g[e[0]].add(e[1])
            g[e[1]].add(e[0])
        }
        var ans = Int.MAX_VALUE
        for (i in 0 until n) {
            val dist = IntArray(n) { -1 }
            val par = IntArray(n) { -1 }
            val q = ArrayDeque<Int>()
            dist[i] = 0
            q.add(i)
            while (q.isNotEmpty()) {
                val u = q.removeFirst()
                for (v in g[u]) {
                    if (dist[v] == -1) {
                        dist[v] = dist[u] + 1
                        par[v] = u
                        q.add(v)
                    } else if (par[u] != v) {
                        ans = minOf(ans, dist[u] + dist[v] + 1)
                    }
                }
            }
        }
        return if (ans == Int.MAX_VALUE) -1 else ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
    def findShortestCycle(self, n: int, edges: list[list[int]]) -> int:
        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)
        ans = float('inf')
        for i in range(n):
            dist = [-1] * n
            par = [-1] * n
            q = [i]
            dist[i] = 0
            for u in q:
                for v in g[u]:
                    if dist[v] == -1:
                        dist[v] = dist[u] + 1
                        par[v] = u
                        q.append(v)
                    elif par[u] != v:
                        ans = min(ans, dist[u] + dist[v] + 1)
        return -1 if ans == float('inf') else ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


impl Solution {
    pub fn find_shortest_cycle(n: i32, edges: Vec<Vec<i32>>) -> i32 {
        let n = n as usize;
        let mut g = vec![vec![]; n];
        for e in &edges {
            let u = e[0] as usize;
            let v = e[1] as usize;
            g[u].push(v);
            g[v].push(u);
        }
        let mut ans = i32::MAX;
        for i in 0..n {
            let mut dist = vec![-1; n];
            let mut par = vec![-1; n];
            let mut q = std::collections::VecDeque::new();
            dist[i] = 0;
            q.push_back(i as i32);
            while let Some(u) = q.pop_front() {
                for &v in &g[u as usize] {
                    if dist[v as usize] == -1 {
                        dist[v as usize] = dist[u as usize] + 1;
                        par[v as usize] = u;
                        q.push_back(v);
                    } else if par[u as usize] != v {
                        ans = ans.min(dist[u as usize] + dist[v as usize] + 1);
                    }
                }
            }
        }
        if ans == i32::MAX { -1 } else { ans }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution {
    findShortestCycle(n: number, edges: number[][]): number {
        const g: number[][] = Array.from({length: n}, () => []);
        for (const [u, v] of edges) {
            g[u].push(v);
            g[v].push(u);
        }
        let ans = Number.MAX_SAFE_INTEGER;
        for (let i = 0; i < n; ++i) {
            const dist = Array(n).fill(-1);
            const par = Array(n).fill(-1);
            const q: number[] = [i];
            dist[i] = 0;
            for (let k = 0; k < q.length; ++k) {
                const u = q[k];
                for (const v of g[u]) {
                    if (dist[v] === -1) {
                        dist[v] = dist[u] + 1;
                        par[v] = u;
                        q.push(v);
                    } else if (par[u] !== v) {
                        ans = Math.min(ans, dist[u] + dist[v] + 1);
                    }
                }
            }
        }
        return ans === Number.MAX_SAFE_INTEGER ? -1 : ans;
    }
}

Complexity

⏰ Time complexity: O(n * (n + m)), where n = number of nodes, m = number of edges. For each node, we do a BFS over the graph.
🧺 Space complexity: O(n + m), for the adjacency list and BFS queues/arrays.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – BFS from Every Node#

Intuition#

Approach#

Code#

Complexity#