Shortest cycle in an undirected graph

Last Updated : 1 Nov, 2025

Given an undirected graph represented using an adjacency list adj[][]. Find the length of the shortest cycle in the graph.
A cycle is a path that starts and ends at the same vertex without repeating any edge or vertex (except the start/end vertex). The shortest cycle is the cycle with the minimum number of edges.
If the graph does not contain any cycle, return -1.

Examples:  

Input: adj[][] = [[5, 6], [4, 5, 6], [3, 6], [2, 4], [1, 3], [0, 1], [0, 1, 2]]

frame_3201

Output: 4 
Explanation: Shortest Cycle: 6 -> 1 -> 5 -> 0 -> 6

Input: adj[][] = [[5, 6], [2, 4, 5, 6], [1, 3, 6], [2, 4], [1, 3], [0, 1], [0, 1, 2]]

frame_32012

Output: 3 
Explanation: Shortest Cycle: 6 -> 1 -> 2 -> 6 

Try it on GfG Practice
redirect icon

Table of Content

[Approach-1] Using BFS - O( V * (V+E)) Time and O(V) Space

The idea is to use Breadth-First Search (BFS) to detect the shortest cycle in a graph.
We know that BFS works level by level, so while traversing, it always finds the shortest cycle first from the starting node.
Therefore, we perform BFS from each vertex of the graph and finally take the minimum among all to get the overall shortest cycle length.

To achieve this, we perform BFS from each vertex in the graph:

  • For every vertex, start a BFS traversal.
  • Maintain a parent[] array to track the previous node (to avoid counting the same edge twice).
  • While performing BFS, if we reach a vertex that has already been visited and it is not the parent, a shortest cycle is found.
  • The current BFS level gives the length of that cycle, since BFS ensures minimal distance.
  • Repeat the above process for all vertices, keeping track of the minimum cycle length found.
C++ 
//Driver Code Starts
#include <iostream>
#include <vector>
#include <climits>
#include <queue>
using namespace std;
//Driver Code Ends


// BFS function to find shortest cycle starting from a given node
int bfs(int start, vector<vector<int>> &adj) {
    int V = adj.size();

    // Distance and parent arrays
    vector<int> dist(V, (int)(1e9));
    vector<int> par(V, -1);

    queue<int> q;
    dist[start] = 0;
    q.push(start);

    int ans = INT_MAX;

    while (!q.empty()) {
        int x = q.front();
        q.pop();

        for (int child : adj[x]) {

            // If not visited yet
            if (dist[child] == (int)(1e9)) {
                dist[child] = dist[x] + 1;
                par[child] = x;
                q.push(child);
            }

            // If already visited and not the parent, cycle found
            else if (par[x] != child && par[child] != x) {
                ans = min(ans, dist[x] + dist[child] + 1);
            }
        }
    }

    return ans;
}

// Function to find length of shortest cycle in the graph
int shortCycle(vector<vector<int>> &adj) {
    int V = adj.size();
    int ans = INT_MAX;

    // Run BFS from every vertex
    for (int i = 0; i < V; i++) {
        ans = min(ans, bfs(i, adj));
    }

    // If no cycle found
    if (ans == INT_MAX)
        return -1;

    return ans;
}


//Driver Code Starts
int main() {
   vector<vector<int>> adj = {{5, 6}, {4, 5, 6}, {3, 6}, {2, 4}, {1, 3}, {0, 1}, {0, 1, 2}};


    cout << shortCycle(adj);
    return 0;
}

//Driver Code Ends
Java 
//Driver Code Starts
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Arrays;
import java.lang.Integer;

public class GFG {

//Driver Code Ends

    // BFS function to find shortest cycle starting from a given node
    static int bfs(int start, ArrayList<ArrayList<Integer>> adj) {
        int V = adj.size();

        // Distance and parent arrays
        int[] dist = new int[V];
        int[] par = new int[V];

        Arrays.fill(dist, (int) 1e9);
        Arrays.fill(par, -1);

        Queue<Integer> q = new LinkedList<>();
        dist[start] = 0;
        q.add(start);

        int ans = Integer.MAX_VALUE;

        while (!q.isEmpty()) {
            int x = q.poll();

            for (int child : adj.get(x)) {

                // If not visited yet
                if (dist[child] == (int) 1e9) {
                    dist[child] = dist[x] + 1;
                    par[child] = x;
                    q.add(child);
                }

                // If already visited and not the parent, cycle found
                else if (par[x] != child && par[child] != x) {
                    ans = Math.min(ans, dist[x] + dist[child] + 1);
                }
            }
        }

        return ans;
    }

    // Function to find length of shortest cycle in the graph
    static int shortCycle(ArrayList<ArrayList<Integer>> adj) {
        int V = adj.size();
        int ans = Integer.MAX_VALUE;

        // Run BFS from every vertex
        for (int i = 0; i < V; i++) {
            ans = Math.min(ans, bfs(i, adj));
        }

        // If no cycle found
        if (ans == Integer.MAX_VALUE)
            return -1;

        return ans;
    }
    

//Driver Code Starts
    
    // Function to add an edge to the adjacency list
    static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u); 
    }

    public static void main(String[] args) {
        int V = 7;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

        // Create empty adjacency list
        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<>());

        addEdge(adj, 0, 5);
        addEdge(adj, 0, 6);
        addEdge(adj, 1, 4);
        addEdge(adj, 1, 5);
        addEdge(adj, 1, 6);
        addEdge(adj, 2, 3);
        addEdge(adj, 2, 6);
        addEdge(adj, 3, 4);
        addEdge(adj, 4, 1);
        addEdge(adj, 5, 0);
        addEdge(adj, 5, 1);
        addEdge(adj, 6, 0);
        addEdge(adj, 6, 1);
        addEdge(adj, 6, 2);

        System.out.println(shortCycle(adj));
    }
}

//Driver Code Ends
Python 
#Driver Code Starts
from collections import deque
import sys
#Driver Code Ends


# BFS function to find shortest cycle starting from a given node
def bfs(start, adj):
    V = len(adj)

    # Distance and parent arrays
    dist = [int(1e9)] * V
    par = [-1] * V

    q = deque()
    dist[start] = 0
    q.append(start)

    ans = sys.maxsize

    while q:
        x = q.popleft()

        for child in adj[x]:

            # If not visited yet
            if dist[child] == int(1e9):
                dist[child] = dist[x] + 1
                par[child] = x
                q.append(child)

            # If already visited and not the parent, cycle found
            elif par[x] != child and par[child] != x:
                ans = min(ans, dist[x] + dist[child] + 1)

    return ans

# Function to find length of shortest cycle in the graph
def shortCycle(adj):
    V = len(adj)
    ans = sys.maxsize

    # Run BFS from every vertex
    for i in range(V):
        ans = min(ans, bfs(i, adj))

    # If no cycle found
    if ans == sys.maxsize:
        return -1

    return ans


#Driver Code Starts
if __name__ == "__main__":
    adj = [[5, 6], [4, 5, 6], [3, 6], [2, 4], [1, 3], [0, 1], [0, 1, 2]]
    print(shortCycle(adj))

#Driver Code Ends
C# 
//Driver Code Starts
using System;
using System.Collections.Generic;

public class GFG
{
  
//Driver Code Ends

    // BFS function to find shortest cycle starting from a given node
    static int bfs(int start, List<List<int>> adj)
    {
        int V = adj.Count;

        // Distance and parent arrays
        int[] dist = new int[V];
        int[] par = new int[V];

        for (int i = 0; i < V; i++)
        {
            dist[i] = (int)1e9;
            par[i] = -1;
        }

        Queue<int> q = new Queue<int>();
        dist[start] = 0;
        q.Enqueue(start);

        int ans = int.MaxValue;

        while (q.Count > 0)
        {
            int x = q.Dequeue();

            foreach (int child in adj[x])
            {
                // If not visited yet
                if (dist[child] == (int)1e9)
                {
                    dist[child] = dist[x] + 1;
                    par[child] = x;
                    q.Enqueue(child);
                }

                // If already visited and not the parent, cycle found
                else if (par[x] != child && par[child] != x)
                {
                    ans = Math.Min(ans, dist[x] + dist[child] + 1);
                }
            }
        }

        return ans;
    }

    // Function to find length of shortest cycle in the graph
    static int shortCycle(List<List<int>> adj)
    {
        int V = adj.Count;
        int ans = int.MaxValue;

        // Run BFS from every vertex
        for (int i = 0; i < V; i++)
        {
            ans = Math.Min(ans, bfs(i, adj));
        }

        // If no cycle found
        if (ans == int.MaxValue)
            return -1;

        return ans;
    }

//Driver Code Starts
      // Function to add an edge to the adjacency list
    static void addEdge(List<List<int>> adj, int u, int v)
    {
        adj[u].Add(v);
        adj[v].Add(u); 
    }

    public static void Main()
    {
        int V = 7;
        List<List<int>> adj = new List<List<int>>();

        // Create empty adjacency list
        for (int i = 0; i < V; i++)
            adj.Add(new List<int>());

        // Add edges
        addEdge(adj, 0, 5);
        addEdge(adj, 0, 6);
        addEdge(adj, 1, 4);
        addEdge(adj, 1, 5);
        addEdge(adj, 1, 6);
        addEdge(adj, 2, 3);
        addEdge(adj, 2, 6);
        addEdge(adj, 3, 4);
        addEdge(adj, 4, 1);
        addEdge(adj, 5, 0);
        addEdge(adj, 5, 1);
        addEdge(adj, 6, 0);
        addEdge(adj, 6, 1);
        addEdge(adj, 6, 2);

        Console.WriteLine(shortCycle(adj));
    }
}

//Driver Code Ends
JavaScript 
//Driver Code Starts
const Deque = require("denque");
//Driver Code Ends


// BFS function to find shortest cycle starting from a given node
function bfs(start, adj) {
    const V = adj.length;

    // Distance and parent arrays
    let dist = new Array(V).fill(1e9);
    let par = new Array(V).fill(-1);

    const q = new Deque();
    dist[start] = 0;
    q.push(start);

    let ans = Number.MAX_SAFE_INTEGER;

    while (q.length > 0) {
        let x = q.shift();

        for (let child of adj[x]) {

            // If not visited yet
            if (dist[child] === 1e9) {
                dist[child] = dist[x] + 1;
                par[child] = x;
                q.push(child);
            }

            // If already visited and not the parent, cycle found
            else if (par[x] !== child && par[child] !== x) {
                ans = Math.min(ans, dist[x] + dist[child] + 1);
            }
        }
    }

    return ans;
}

// Function to find length of shortest cycle in the graph
function shortCycle(adj) {
    const V = adj.length;
    let ans = Number.MAX_SAFE_INTEGER;

    // Run BFS from every vertex
    for (let i = 0; i < V; i++) {
        ans = Math.min(ans, bfs(i, adj));
    }

    // If no cycle found
    if (ans === Number.MAX_SAFE_INTEGER)
        return -1;

    return ans;
}


//Driver Code Starts
// Driver code
const adj = [[5, 6], [4, 5, 6], [3, 6], [2, 4], [1, 3], [0, 1], [0, 1, 2]];

console.log(shortCycle(adj));

//Driver Code Ends

Output
4

[Approach-2] Using Edge Removal - O(E*(V+E)) Time and O(V+E) Space

The idea behind this approach is by temporarily removing each edge one by one and then using BFS to check if the two vertices connected by that edge are still reachable.
If, after removing an edge (u, v), we can still reach v from u using BFS, then there exists another path between them — which means a cycle is formed.
The length of this cycle will be equal to the shortest path distance between u and v (found using BFS) plus one (for the removed edge itself). We repeat this process for every edge in the graph, compute the cycle length for each, and take the minimum among them as the shortest cycle length.

C++ 
//Driver Code Starts
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
//Driver Code Ends


int shortCycle(vector<vector<int>> &adj) {

    int V = adj.size();
    int ans = INT_MAX;

    // Collect all unique edges (u < v to avoid duplicates)
    vector<vector<int>> edges;
    for (int u = 0; u < V; u++) {
        for (int v : adj[u]) {
            if (u < v)
                edges.push_back({u, v});
        }
    }

    // For each edge (u, v), perform BFS ignoring that edge
    for (auto &e : edges) {
        int u = e[0], v = e[1];

        vector<int> dist(V, -1);
        queue<int> q;

        // Start BFS from node u
        dist[u] = 0;
        q.push(u);

        while (!q.empty()) {
            int node = q.front();
            q.pop();

            for (int nei : adj[node]) {
                // Skip the removed edge (u, v)
                if ((node == u && nei == v) || (node == v && nei == u))
                    continue;

                // If not visited, update distance and push to queue
                if (dist[nei] == -1) {
                    dist[nei] = dist[node] + 1;
                    q.push(nei);
                }
            }
        }

        // If v is reachable from u, we found a cycle
        if (dist[v] != -1)
            ans = min(ans, dist[v] + 1);
    }

    // If no cycle is found, return -1
    return (ans == INT_MAX) ? -1 : ans;
}


//Driver Code Starts
int main() {
    // Given adjacency list
    vector<vector<int>> adj = {{5, 6}, {4, 5, 6}, {3, 6}, {2, 4}, {1, 3}, {0, 1}, {0, 1, 2}};

    // Call the function
    int result = shortCycle(adj);

    cout << result << endl;

    return 0;
}

//Driver Code Ends
Java 
//Driver Code Starts
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;

public class GFG {
//Driver Code Ends


    // Function to find the shortest cycle in an undirected graph
    public static int shortCycle(ArrayList<ArrayList<Integer>> adj) {

        int V = adj.size();
        int ans = Integer.MAX_VALUE;

        // Collect all unique edges (u < v to avoid duplicates)
        ArrayList<ArrayList<Integer>> edges = new ArrayList<>();
        for (int u = 0; u < V; u++) {
            for (int v : adj.get(u)) {
                if (u < v) {
                    ArrayList<Integer> edge = new ArrayList<>();
                    edge.add(u);
                    edge.add(v);
                    edges.add(edge);
                }
            }
        }

        // For each edge (u, v), perform BFS ignoring that edge
        for (ArrayList<Integer> e : edges) {
            int u = e.get(0), v = e.get(1);

            int[] dist = new int[V];
            Arrays.fill(dist, -1);
            Queue<Integer> q = new LinkedList<>();

            // Start BFS from node u
            dist[u] = 0;
            q.add(u);

            while (!q.isEmpty()) {
                int node = q.poll();

                for (int nei : adj.get(node)) {
                    // Skip the removed edge (u, v)
                    if ((node == u && nei == v) || (node == v && nei == u))
                        continue;

                    // If not visited, update distance and push to queue
                    if (dist[nei] == -1) {
                        dist[nei] = dist[node] + 1;
                        q.add(nei);
                    }
                }
            }

            // If v is reachable from u, we found a cycle
            if (dist[v] != -1)
                ans = Math.min(ans, dist[v] + 1);
        }

        // If no cycle is found, return -1
        return (ans == Integer.MAX_VALUE) ? -1 : ans;
    }


//Driver Code Starts
    // Helper function to add an undirected edge
    public static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);
    }

    public static void main(String[] args) {

        int V = 7;

        // Create adjacency list
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }

        // Add edges
        addEdge(adj, 0, 5);
        addEdge(adj, 0, 6);
        addEdge(adj, 1, 4);
        addEdge(adj, 1, 5);
        addEdge(adj, 1, 6);
        addEdge(adj, 2, 3);
        addEdge(adj, 2, 6);
        addEdge(adj, 3, 4);
        addEdge(adj, 4, 1);
        addEdge(adj, 5, 0);
        addEdge(adj, 6, 2);
        addEdge(adj, 6, 1);
        addEdge(adj, 6, 0);

        // Call the function
        int result = shortCycle(adj);

        System.out.println(result);
    }
}

//Driver Code Ends
Python 
#Driver Code Starts
from collections import deque
import sys
#Driver Code Ends


def shortCycle(adj):

    V = len(adj)
    ans = sys.maxsize

    # Collect all unique edges (u < v to avoid duplicates)
    edges = []
    for u in range(V):
        for v in adj[u]:
            if u < v:
                edges.append([u, v])

    # For each edge (u, v), perform BFS ignoring that edge
    for e in edges:
        u, v = e[0], e[1]

        dist = [-1] * V
        q = deque()

        # Start BFS from node u
        dist[u] = 0
        q.append(u)

        while q:
            node = q.popleft()

            for nei in adj[node]:
                
                # Skip the removed edge (u, v)
                if (node == u and nei == v) or (node == v and nei == u):
                    continue

                # If not visited, update distance and push to queue
                if dist[nei] == -1:
                    dist[nei] = dist[node] + 1
                    q.append(nei)

        # If v is reachable from u, we found a cycle
        if dist[v] != -1:
            ans = min(ans, dist[v] + 1)

    # If no cycle is found, return -1
    return -1 if ans == sys.maxsize else ans



#Driver Code Starts
if __name__ == "__main__":
    
    # Given adjacency list
    adj = [[5, 6], [4, 5, 6], [3, 6], [2, 4], [1, 3], [0, 1], [0, 1, 2]]

    # Call the function
    result = shortCycle(adj)

    print(result)

#Driver Code Ends
C# 
//Driver Code Starts
using System;
using System.Collections.Generic;

public class GFG
{
//Driver Code Ends

    // Function to find the shortest cycle in an undirected graph
    public static int shortCycle(List<List<int>> adj)
    {
        int V = adj.Count;
        int ans = int.MaxValue;

        // Collect all unique edges (u < v to avoid duplicates)
        List<List<int>> edges = new List<List<int>>();
        for (int u = 0; u < V; u++)
        {
            foreach (int v in adj[u])
            {
                if (u < v)
                {
                    edges.Add(new List<int> { u, v });
                }
            }
        }

        // For each edge (u, v), perform BFS ignoring that edge
        foreach (var e in edges)
        {
            int u = e[0], v = e[1];

            int[] dist = new int[V];
            Array.Fill(dist, -1);
            Queue<int> q = new Queue<int>();

            // Start BFS from node u
            dist[u] = 0;
            q.Enqueue(u);

            while (q.Count > 0)
            {
                int node = q.Dequeue();

                foreach (int nei in adj[node])
                {
                    // Skip the removed edge (u, v)
                    if ((node == u && nei == v) || (node == v && nei == u))
                        continue;

                    // If not visited, update distance and push to queue
                    if (dist[nei] == -1)
                    {
                        dist[nei] = dist[node] + 1;
                        q.Enqueue(nei);
                    }
                }
            }

            // If v is reachable from u, we found a cycle
            if (dist[v] != -1)
                ans = Math.Min(ans, dist[v] + 1);
        }

        // If no cycle is found, return -1
        return (ans == int.MaxValue) ? -1 : ans;
    }


//Driver Code Starts
    // Helper function to add an undirected edge
    public static void addEdge(List<List<int>> adj, int u, int v)
    {
        adj[u].Add(v);
        adj[v].Add(u);
    }

    public static void Main()
    {
        int V = 7;

        // Create adjacency list
        List<List<int>> adj = new List<List<int>>();
        for (int i = 0; i < V; i++)
        {
            adj.Add(new List<int>());
        }

        // Add edges
        addEdge(adj, 0, 5);
        addEdge(adj, 0, 6);
        addEdge(adj, 1, 4);
        addEdge(adj, 1, 5);
        addEdge(adj, 1, 6);
        addEdge(adj, 2, 3);
        addEdge(adj, 2, 6);
        addEdge(adj, 3, 4);
        addEdge(adj, 4, 1);
        addEdge(adj, 5, 0);
        addEdge(adj, 6, 2);
        addEdge(adj, 6, 1);
        addEdge(adj, 6, 0);

        // Call the function
        int result = shortCycle(adj);

        Console.WriteLine(result);
    }
}

//Driver Code Ends
JavaScript 
function shortCycle(adj) {

    const V = adj.length;
    let ans = Number.MAX_SAFE_INTEGER;

    // Collect all unique edges (u < v to avoid duplicates)
    const edges = [];
    for (let u = 0; u < V; u++) {
        for (let v of adj[u]) {
            if (u < v)
                edges.push([u, v]);
        }
    }

    // For each edge (u, v), perform BFS ignoring that edge
    for (let e of edges) {
        const u = e[0], v = e[1];

        const dist = new Array(V).fill(-1);
        const q = [];

        // Start BFS from node u
        dist[u] = 0;
        q.push(u);

        while (q.length > 0) {
            const node = q.shift();

            for (let nei of adj[node]) {
                // Skip the removed edge (u, v)
                if ((node === u && nei === v) || (node === v && nei === u))
                    continue;

                // If not visited, update distance and push to queue
                if (dist[nei] === -1) {
                    dist[nei] = dist[node] + 1;
                    q.push(nei);
                }
            }
        }

        // If v is reachable from u, we found a cycle
        if (dist[v] !== -1)
            ans = Math.min(ans, dist[v] + 1);
    }

    // If no cycle is found, return -1
    return (ans === Number.MAX_SAFE_INTEGER) ? -1 : ans;
}

//Driver Code
//Driver Code Starts
// Given adjacency list
const adj = [[5, 6], [4, 5, 6], [3, 6], [2, 4], [1, 3], [0, 1], [0, 1, 2]];

// Call the function
const result = shortCycle(adj);

console.log(result);

//Driver Code Ends

Output
4

Why not dfs?

DFS (Depth-First Search) goes as deep as possible before backtracking. This can easily cause it to find longer cycles first, because it doesn’t explore in increasing order of path length.
DFS can detect if a cycle exists but it cannot ensure that the first cycle found is the shortest one.

Comment

Explore