We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Shortest Cycle in a Graph

Number: 2671

Difficulty: Hard

Paid? No

Companies: Zomato

Problem Description

Given an undirected graph with n vertices labeled from 0 to n-1 and a list of edges, determine the length of the shortest cycle present in the graph. A cycle is a path that starts and ends at the same vertex with each edge used only once. If no cycle exists, return -1.

Key Insights

  • The graph is undirected and each edge is bidirectional.
  • Use Breadth-First Search (BFS) starting from each vertex to compute the shortest cycle that passes through that vertex.
  • While performing BFS, if you encounter a vertex that has already been visited (and is not the immediate parent), then a cycle is detected and you can compute its length as the sum of distances from the starting vertex to the current vertex and the encountered vertex plus one.
  • Repeat the process for every vertex and return the minimum cycle length found.

Space and Time Complexity

Time Complexity: O(n * (n + e)), where n is the number of vertices and e is the number of edges, since we perform BFS from each vertex. Space Complexity: O(n + e), used for storing the graph and the auxiliary arrays for BFS (distance and parent).

Solution

We solve the problem using a BFS-based approach from each vertex in the graph. First, we represent the graph as an adjacency list. For every vertex, we perform a BFS to track the distances from the starting vertex. During the traversal, for every neighbor of the current vertex, if it is not visited, we mark it and record its parent. If it is already visited and it is not the parent of the current vertex, then a cycle is detected. The length of the cycle can be computed as the sum of the distances from the starting vertex to the current and neighbor vertices plus one (for the connecting edge). We keep track of the minimum cycle length across all BFS traversals. If no cycle is found in any BFS, we return -1.

Code Solutions

from collections import deque

def shortestCycle(n, edges):
    # Build the graph as an adjacency list.
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    min_cycle = float('inf')
    
    # BFS from every vertex.
    for i in range(n):
        # Initialize distance and parent arrays.
        distance = [-1] * n  # distance from node i to every other node.
        parent = [-1] * n    # parent of each node in the BFS tree.
        distance[i] = 0
        queue = deque([i])
        
        while queue:
            curr = queue.popleft()
            for neighbor in graph[curr]:
                # If neighbor is not visited, mark it, set its parent, and update the distance.
                if distance[neighbor] == -1:
                    distance[neighbor] = distance[curr] + 1
                    parent[neighbor] = curr
                    queue.append(neighbor)
                # A visited neighbor that is not the parent indicates a cycle.
                elif parent[curr] != neighbor:
                    cycle_length = distance[curr] + distance[neighbor] + 1
                    min_cycle = min(min_cycle, cycle_length)
    
    return min_cycle if min_cycle != float('inf') else -1
← Back to All Questions