31. Shortest Cycle
✅ GFG solution to the Shortest Cycle in Undirected Graph problem: find minimum length cycle in an undirected graph using multi-source BFS technique. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
You are given an undirected graph with V vertices numbered from 0 to V-1 and E edges, represented as a 2D array edges[][], where each element edges[i] = [u, v] represents an undirected edge between vertex u and v.
Find the length of the shortest cycle in the graph. If the graph does not contain any cycle, return -1.
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 one with the minimum number of edges.
📘 Examples
Example 1
Input: V = 7, E = 8, edges[][] = [[0, 5], [0, 6], [5, 1], [6, 1], [6, 2], [2, 3], [3, 4], [1, 4]]
Output: 4
Explanation: Possible cycles are:
0 → 5 → 1 → 6 → 0 (length = 4)
1 → 4 → 3 → 2 → 6 → 1 (length = 5)
The smallest one is 0 → 5 → 1 → 6 → 0, with length 4.Example 2
Input: V = 7, E = 9, edges[][] = [[0, 5], [0, 6], [1, 2], [1, 4], [1, 5], [1, 6], [2, 6], [2, 3], [3, 4]]
Output: 3
Explanation: Possible cycles include:
1 → 2 → 6 → 1 (length = 3)
1 → 2 → 3 → 4 → 1 (length = 4)
0 → 5 → 1 → 6 → 0 (length = 4)
The smallest one is 1 → 2 → 6 → 1, with length 3.🔒 Constraints
$1 \le V \le 10^3$
$0 \le E \le 10^3$
$0 \le \text{edges}[i][0], \text{edges}[i][1] < V$
✅ My Approach
The optimal approach uses Multi-Source BFS to detect the shortest cycle by running BFS from every vertex:
Multi-Source BFS Approach
Build Adjacency List:
Convert the edge list to an adjacency list representation for efficient neighbor access.
For each edge
[u, v], addvtoadj[u]andutoadj[v].
Run BFS from Each Vertex:
For each vertex
ifrom 0 to V-1, run a BFS to detect cycles.Maintain two arrays:
d[]for distance from source andp[]for parent tracking.
Detect Cycle During BFS:
When visiting a neighbor
vfrom current nodeu:If
vis unvisited (d[v] == -1), mark distance and parent, then enqueue.If
vis visited and not the parent ofu(p[u] != v), a cycle is found.Calculate cycle length as
d[u] + d[v] + 1(distance from source to both endpoints plus the edge connecting them).
Track Minimum Cycle:
Update result with the minimum cycle length found across all BFS runs.
Return Result:
If no cycle is detected, return -1; otherwise, return the minimum cycle length.
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(V × (V + E)), as we run BFS from each of the V vertices, and each BFS traversal visits all vertices and edges in the worst case. For each vertex, BFS takes O(V + E) time.
Expected Auxiliary Space Complexity: O(V + E), where O(E) is used for storing the adjacency list representation of the graph, and O(V) is used for the distance and parent arrays during each BFS traversal.
🧑💻 Code (C++)
class Solution {
public:
int shortCycle(int V, vector<vector<int>> &edges) {
vector<vector<int>> adj(V);
for (auto &e : edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
}
int res = INT_MAX;
for (int i = 0; i < V; i++) {
vector<int> d(V, -1), p(V, -1);
queue<int> q;
d[i] = 0;
q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (d[v] == -1) {
d[v] = d[u] + 1;
p[v] = u;
q.push(v);
} else if (p[u] != v) res = min(res, d[u] + d[v] + 1);
}
}
}
return res == INT_MAX ? -1 : res;
}
};☕ Code (Java)
class Solution {
public int shortCycle(int V, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < V; i++) {
int[] d = new int[V];
int[] p = new int[V];
Arrays.fill(d, -1);
Arrays.fill(p, -1);
Queue<Integer> q = new LinkedList<>();
d[i] = 0;
q.offer(i);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : adj.get(u)) {
if (d[v] == -1) {
d[v] = d[u] + 1;
p[v] = u;
q.offer(v);
} else if (p[u] != v) res = Math.min(res, d[u] + d[v] + 1);
}
}
}
return res == Integer.MAX_VALUE ? -1 : res;
}
}🐍 Code (Python)
class Solution:
def shortCycle(self, V, edges):
from collections import deque
adj = [[] for _ in range(V)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
res = float('inf')
for i in range(V):
d = [-1] * V
p = [-1] * V
q = deque([i])
d[i] = 0
while q:
u = q.popleft()
for v in adj[u]:
if d[v] == -1:
d[v] = d[u] + 1
p[v] = u
q.append(v)
elif p[u] != v:
res = min(res, d[u] + d[v] + 1)
return -1 if res == float('inf') else res🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated