Shortest Cycle in a Graph solution and explanation
Google
9 more videos on this problem
Shortest Cycle in a Graph | Biweekly Contest 101codingMohan · 10:07 · 5K views
2608. Shortest Cycle in a Graph (Leetcode)Mayank · 10:54 · 2K views
2608. Shortest Cycle in a Graph (Leetcode Hard)Programming Live with Larry · 22:58 · 1K views
2608. Shortest Cycle in a GraphRaman Bhari · 15:31 · 1K views
Leetcode Biweekly Contest 101 | 2608. Shortest Cycle in a Graph | Simple SolutionLogicBehindCode · 12:30 · 1K views
Shortest Cycle in a Graph | Leetcode 2608 | JAVA/C++Akshay Anil · 10:31 · 908 views
Leetcode Biweekly 101 | 2608 . Shortest Cycle in a Graph | SolutionMd Zuhair · 5:20 · 708 views
【每日一题】LeetCode 2608. Shortest Cycle in a GraphHuifeng Guan · 13:27 · 362 views
Shortest Cycle in Graph | LeetCode 2608 - HardAdityaraj Dangi · 6:50 · 87 views
Leetcode 2608. Shortest Cycle in a Graph (bfs)LetsCode · 11:13 · 54 views
The 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 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 != vi- There are no repeated edges.
Approach overview
Problem 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.
Approach 1: BFS to Detect Shortest Cycle
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.
from collections import deque
def shortest_cycle_bfs(n, edges):
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
def bfs(start):
queue = deque([(start, -1, 0)])
visited = {start}
while queue:
node, parent, dist = queue.popleft()
for neighbor in graph[node]:
if neighbor == parent:
continue
if neighbor in visited:
return dist + 1
visited.add(neighbor)
queue.append((neighbor, node, dist + 1))
return float('inf')
min_cycle = float('inf')
for i in range(n):
min_cycle = min(min_cycle, bfs(i))
if min_cycle == 3:
break
return -1 if min_cycle == float('inf') else min_cycleimport java.util.*;
public class ShortestCycle {
public static int shortestCycle(int n, int[][] edges) {
List<Integer>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int[] edge : edges) {
graph[edge[0]].add(edge[1]);
graph[edge[1]].add(edge[0]);
}
int minCycle = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int cycleLength = bfs(i, graph);
minCycle = Math.min(minCycle, cycleLength);
if (minCycle == 3) break;
}
return minCycle == Integer.MAX_VALUE ? -1 : minCycle;
}
private static int bfs(int start, List<Integer>[] graph) {
Queue<int[]> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.offer(new int[]{start, -1, 0});
visited.add(start);
while (!queue.isEmpty()) {
int[] node = queue.poll();
for (int neighbor : graph[node[0]]) {
if (neighbor == node[1]) continue;
if (visited.contains(neighbor)) return node[2] + 1;
visited.add(neighbor);
queue.offer(new int[]{neighbor, node[0], node[2] + 1});
}
}
return Integer.MAX_VALUE;
}
}#include <vector>
#include <queue>
#include <unordered_set>
int shortestCycle(int n, std::vector<std::vector<int>>& edges) {
std::vector<std::vector<int>> graph(n);
for (const auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
auto bfs = [&](int start) {
std::queue<std::tuple<int, int, int>> queue;
std::unordered_set<int> visited;
queue.push({start, -1, 0});
visited.insert(start);
while (!queue.empty()) {
auto [node, parent, dist] = queue.front(); queue.pop();
for (int neighbor : graph[node]) {
if (neighbor == parent) continue;
if (visited.count(neighbor)) return dist + 1;
visited.insert(neighbor);
queue.push({neighbor, node, dist + 1});
}
}
return std::numeric_limits<int>::max();
};
int min_cycle = std::numeric_limits<int>::max();
for (int i = 0; i < n; ++i) {
min_cycle = std::min(min_cycle, bfs(i));
if (min_cycle == 3) break;
}
return min_cycle == std::numeric_limits<int>::max() ? -1 : min_cycle;
}function shortestCycle(n, edges) {
const graph = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
const bfs = (start) => {
const queue = [[start, -1, 0]];
const visited = new Set([start]);
while (queue.length) {
const [node, parent, dist] = queue.shift();
for (const neighbor of graph[node]) {
if (neighbor === parent) continue;
if (visited.has(neighbor)) return dist + 1;
visited.add(neighbor);
queue.push([neighbor, node, dist + 1]);
}
}
return Infinity;
};
let minCycle = Infinity;
for (let i = 0; i < n; i++) {
minCycle = Math.min(minCycle, bfs(i));
if (minCycle === 3) break;
}
return minCycle === Infinity ? -1 : minCycle;
}#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
struct Node {
int vertex;
int parent;
int distance;
};
int** createGraph(int n, int edges[][2], int edgesSize, int* returnColumnSizes) {
int** graph = malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) {
graph[i] = calloc(n, sizeof(int));
}
for (int i = 0; i < edgesSize; i++) {
graph[edges[i][0]][edges[i][1]] = 1;
graph[edges[i][1]][edges[i][0]] = 1;
}
return graph;
}
int bfs(int** graph, int n, int start) {
struct Node* queue = malloc(n * sizeof(struct Node));
bool* visited = calloc(n, sizeof(bool));
int front = 0, rear = 0;
queue[rear++] = (struct Node){start, -1, 0};
visited[start] = true;
while (front < rear) {
struct Node current = queue[front++];
for (int i = 0; i < n; i++) {
if (graph[current.vertex][i]) {
if (i == current.parent) continue;
if (visited[i]) {
free(queue);
free(visited);
return current.distance + 1;
}
visited[i] = true;
queue[rear++] = (struct Node){i, current.vertex, current.distance + 1};
}
}
}
free(queue);
free(visited);
return INT_MAX;
}
int shortestCycle(int n, int edges[][2], int edgesSize) {
int** graph = createGraph(n, edges, edgesSize, NULL);
int min_cycle_length = INT_MAX;
for (int i = 0; i < n; i++) {
min_cycle_length = fmin(min_cycle_length, bfs(graph, n, i));
if (min_cycle_length == 3) break;
}
for (int i = 0; i < n; i++) {
free(graph[i]);
}
free(graph);
return min_cycle_length == INT_MAX ? -1 : min_cycle_length;
}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.
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.
Approach 2: Graph Coloring using DFS to Detect Cycles
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.
def shortestCycle_dfs(n, edges):
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
def dfs(node, parent, color, dist):
color[node] = 'G'
min_cycle = float('inf')
for neighbor in graph[node]:
if neighbor == parent:
continue
if color[neighbor] == 'G':
return dist + 1
if color[neighbor] == 'W':
min_cycle = min(min_cycle, dfs(neighbor, node, color, dist + 1))
color[node] = 'B'
return min_cycle
min_cycle_length = float('inf')
for i in range(n):
color = ['W'] * n
cycle_length = dfs(i, -1, color, 0)
min_cycle_length = min(min_cycle_length, cycle_length)
if min_cycle_length == 3:
break
return -1 if min_cycle_length == float('inf') else min_cycle_lengthimport java.util.*;
public class GraphCycleDFS {
public static int shortestCycleDFS(int n, int[][] edges) {
List<Integer>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int[] edge : edges) {
graph[edge[0]].add(edge[1]);
graph[edge[1]].add(edge[0]);
}
String[] color = new String[n];
Arrays.fill(color, "W");
int minCycle = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
minCycle = Math.min(minCycle, dfs(i, -1, color, graph, 0));
if (minCycle == 3) break;
Arrays.fill(color, "W");
}
return minCycle == Integer.MAX_VALUE ? -1 : minCycle;
}
private static int dfs(int node, int parent, String[] color, List<Integer>[] graph, int distance) {
color[node] = "G";
int minCycle = Integer.MAX_VALUE;
for (int neighbor : graph[node]) {
if (neighbor == parent) continue;
if (color[neighbor].equals("G")) return distance + 1;
if (color[neighbor].equals("W")) {
minCycle = Math.min(minCycle, dfs(neighbor, node, color, graph, distance + 1));
}
}
color[node] = "B";
return minCycle;
}
}#include <vector>
#include <string>
#include <limits>
int dfsTableColoring(int node, int parent, std::vector<std::string>& color, const std::vector<std::vector<int>>& graph, int distance) {
color[node] = "G";
int min_cycle = std::numeric_limits<int>::max();
for (int neighbor : graph[node]) {
if (neighbor == parent) continue;
if (color[neighbor] == "G") return distance + 1;
if (color[neighbor] == "W") {
min_cycle = std::min(min_cycle, dfsTableColoring(neighbor, node, color, graph, distance + 1));
}
}
color[node] = "B";
return min_cycle;
}
int shortestCycleDFS(int n, const std::vector<std::vector<int>>& edges) {
std::vector<std::vector<int>> graph(n);
for (const auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
std::vector<std::string> color(n, "W");
int min_cycle = std::numeric_limits<int>::max();
for (int i = 0; i < n; ++i) {
min_cycle = std::min(min_cycle, dfsTableColoring(i, -1, color, graph, 0));
if (min_cycle == 3) break;
std::fill(color.begin(), color.end(), "W");
}
return min_cycle == std::numeric_limits<int>::max() ? -1 : min_cycle;
}function shortestCycleDFS(n, edges) {
const graph = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
const color = Array(n).fill('W');
const dfs = (node, parent, distance) => {
color[node] = 'G';
let minCycle = Infinity;
for (const neighbor of graph[node]) {
if (neighbor === parent) continue;
if (color[neighbor] === 'G') return distance + 1;
if (color[neighbor] === 'W') {
minCycle = Math.min(minCycle, dfs(neighbor, node, distance + 1));
}
}
color[node] = 'B';
return minCycle;
};
let minCycleLength = Infinity;
for (let i = 0; i < n; i++) {
minCycleLength = Math.min(minCycleLength, dfs(i, -1, 0));
if (minCycleLength === 3) break;
color.fill('W');
}
return minCycleLength === Infinity ? -1 : minCycleLength;
}using System;
using System.Collections.Generic;
public class GraphCycleDFS {
public static int ShortestCycle(int n, int[][] edges) {
List<int>[] graph = new List<int>[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<int>();
}
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
graph[edge[1]].Add(edge[0]);
}
string[] color = new string[n];
int minCycle = int.MaxValue;
for (int i = 0; i < n; i++) {
Array.Fill(color, "W");
minCycle = Math.Min(minCycle, Dfs(i, -1, color, graph, 0));
if (minCycle == 3) break;
}
return minCycle == int.MaxValue ? -1 : minCycle;
}
private static int Dfs(int node, int parent, string[] color, List<int>[] graph, int distance) {
color[node] = "G";
int minCycle = int.MaxValue;
foreach (int neighbor in graph[node]) {
if (neighbor == parent) continue;
if (color[neighbor] == "G") return distance + 1;
if (color[neighbor] == "W") {
minCycle = Math.Min(minCycle, Dfs(neighbor, node, color, graph, distance + 1));
}
}
color[node] = "B";
return minCycle;
}
}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.
Time Complexity: O(n + m) due to DFS exploration.
Space Complexity: O(n), with color array and recursion depth.
Approach 3: Enumerate edges + BFS
We first construct the adjacency list g of the graph according to the array edges, where g[u] represents all the adjacent vertices of vertex u.
Then we enumerate the two-directional edge (u, v), if the path from vertex u to vertex v still exists after deleting this edge, then the length of the shortest cycle containing this edge is dist[v] + 1, where dist[v] represents the shortest path length from vertex u to vertex v. We take the minimum of all these cycles.
The time complexity is O(m^2) and the space complexity is O(m + n), where m and n are the length of the array edges and the number of vertices.
function findShortestCycle(n: number, edges: number[][]): number {
const g: number[][] = new Array(n).fill(0).map(() => []);
for (const [u, v] of edges) {
g[u].push(v);
g[v].push(u);
}
const inf = 1 << 30;
let ans = inf;
const bfs = (u: number, v: number) => {
const dist: number[] = new Array(n).fill(inf);
dist[u] = 0;
const q: number[] = [u];
while (q.length) {
const i = q.shift()!;
for (const j of g[i]) {
if ((i == u && j == v) || (i == v && j == u) || dist[j] != inf) {
continue;
}
dist[j] = dist[i] + 1;
q.push(j);
}
}
return 1 + dist[v];
};
for (const [u, v] of edges) {
ans = Math.min(ans, bfs(u, v));
}
return ans < inf ? ans : -1;
}func findShortestCycle(n int, edges [][]int) int {
g := make([][]int, n)
for _, e := range edges {
u, v := e[0], e[1]
g[u] = append(g[u], v)
g[v] = append(g[v], u)
}
const inf = 1 << 30
bfs := func(u, v int) int {
dist := make([]int, n)
for i := range dist {
dist[i] = inf
}
dist[u] = 0
q := []int{u}
for len(q) > 0 {
i := q[0]
q = q[1:]
for _, j := range g[i] {
if (i == u && j == v) || (i == v && j == u) || dist[j] != inf {
continue
}
dist[j] = dist[i] + 1
q = append(q, j)
}
}
return dist[v] + 1
}
ans := inf
for _, e := range edges {
u, v := e[0], e[1]
ans = min(ans, bfs(u, v))
}
if ans < inf {
return ans
}
return -1
}Approach 4: Enumerate points + BFS
Similar to Solution 1, we first construct the adjacency list g of the graph according to the array edges, where g[u] represents all the adjacent vertices of vertex u.
Then we enumerate the vertex u, if there are two paths from vertex u to vertex v, then we currently find a cycle, the length is the sum of the length of the two paths. We take the minimum of all these cycles.
The time complexity is O(m times n) and the space complexity is O(m + n), where m and n are the length of the array edges and the number of vertices.
function findShortestCycle(n: number, edges: number[][]): number {
const g: number[][] = new Array(n).fill(0).map(() => []);
for (const [u, v] of edges) {
g[u].push(v);
g[v].push(u);
}
const inf = 1 << 30;
let ans = inf;
const bfs = (u: number) => {
const dist: number[] = new Array(n).fill(-1);
dist[u] = 0;
const q: number[][] = [[u, -1]];
let ans = inf;
while (q.length) {
const p = q.shift()!;
u = p[0];
const fa = p[1];
for (const v of g[u]) {
if (dist[v] < 0) {
dist[v] = dist[u] + 1;
q.push([v, u]);
} else if (v !== fa) {
ans = Math.min(ans, dist[u] + dist[v] + 1);
}
}
}
return ans;
};
for (let i = 0; i < n; ++i) {
ans = Math.min(ans, bfs(i));
}
return ans < inf ? ans : -1;
}func findShortestCycle(n int, edges [][]int) int {
g := make([][]int, n)
for _, e := range edges {
u, v := e[0], e[1]
g[u] = append(g[u], v)
g[v] = append(g[v], u)
}
const inf = 1 << 30
bfs := func(u int) int {
dist := make([]int, n)
for i := range dist {
dist[i] = -1
}
dist[u] = 0
q := [][2]int{{u, -1}}
ans := inf
for len(q) > 0 {
p := q[0]
u = p[0]
fa := p[1]
q = q[1:]
for _, v := range g[u] {
if dist[v] < 0 {
dist[v] = dist[u] + 1
q = append(q, [2]int{v, u})
} else if v != fa {
ans = min(ans, dist[u]+dist[v]+1)
}
}
}
return ans
}
ans := inf
for i := 0; i < n; i++ {
ans = min(ans, bfs(i))
}
if ans < inf {
return ans
}
return -1
}Complexity comparison
| 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. |
| Enumerate edges + BFS | – |
| Enumerate points + BFS | – |
Complexity analysis
| 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 |
Frequently asked questions
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.