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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Cycle in a Graph

Difficulty: Hard

Problem Description

Given a bi-directional graph with n vertices, represented by a 2D integer array edges, return the length of the shortest cycle in the graph. If no cycle exists, return -1. A cycle is defined as a path that starts and ends at the same node, using each edge only once.

Key Insights

  • The problem requires finding cycles in an undirected graph.
  • A cycle can be detected using Breadth-First Search (BFS) or Depth-First Search (DFS).
  • The shortest cycle can be found by tracking the distance from the starting node during the search.
  • We need to ensure that we do not count the immediate backtracking edge as part of the cycle.

Space and Time Complexity

Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. Each vertex and edge is processed at most once. Space Complexity: O(V), for storing the graph and the BFS queue.

Solution

To solve the problem, we can use a Breadth-First Search (BFS) approach. We will iterate through each vertex and perform a BFS to explore all reachable nodes, keeping track of the distance from the starting node. If we encounter a previously visited node that is not the immediate parent, we have found a cycle. We will record the length of this cycle and update the minimum length found.

  1. Represent the graph using an adjacency list.
  2. For each vertex, initiate a BFS.
  3. Use a queue to manage the vertices to be explored, along with their distances from the starting vertex.
  4. On visiting a node, check for cycles by examining previously visited nodes.
  5. Keep track of the minimum cycle length found.

Code Solutions

from collections import deque, defaultdict

def shortestCycle(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    min_cycle_length = float('inf')

    for start in range(n):
        queue = deque([(start, -1, 0)])  # (current_node, parent_node, distance)
        visited = {start: 0}  # Store distance from start node

        while queue:
            node, parent, dist = queue.popleft()

            for neighbor in graph[node]:
                if neighbor == parent:  # Skip the edge back to parent
                    continue
                if neighbor in visited:  # Cycle found
                    cycle_length = dist + 1 + visited[neighbor]
                    min_cycle_length = min(min_cycle_length, cycle_length)
                else:
                    visited[neighbor] = dist + 1
                    queue.append((neighbor, node, dist + 1))

    return min_cycle_length if min_cycle_length != float('inf') else -1
← Back to All Questions