Shortest Cycle

JavaView on GFG

Intuition

Find length of shortest cycle in an undirected graph. BFS from each node.

Algorithm

1For each node: BFS tracking distances. When back edge found to already-visited node: cycle length = dist[u]+dist[v]+1.

Common Pitfalls

•O(V*(V+E)). BFS-based cycle detection. Shortest cycle = girth of graph.

Shortest Cycle.java

Java

// Approach: BFS from each node. When revisiting a node in BFS tree, compute cycle length. Track minimum.
// Time: O(V * (V+E)) Space: O(V)
import java.util.*;

class Solution {
    public int shortCycle(int V, int[][] edges) {
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < V; i++)
            g.add(new ArrayList<>());

        for (int[] e : edges) {
            int u = e[0], v = e[1];
            g.get(u).add(v);
            g.get(v).add(u);
        }

        int ans = Integer.MAX_VALUE;

        for (int start = 0; start < V; start++) {
            int[] dist = new int[V];
            int[] parent = new int[V];
            Arrays.fill(dist, -1);
            Arrays.fill(parent, -1);

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

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

                for (int nbr : g.get(node)) {
                    if (dist[nbr] == -1) {
                        dist[nbr] = dist[node] + 1;
                        parent[nbr] = node;
                        queue.add(nbr);
                    } else if (parent[node] != nbr) {
                        int cycleLen = dist[node] + dist[nbr] + 1;
                        ans = Math.min(ans, cycleLen);
                    }
                }
            }
        }
        
        return (ans == Integer.MAX_VALUE) ? -1 : ans;
    }
}

Was this solution helpful?