Shortest Cycle In A Graph - Leetcode Solution

The problem "Shortest Cycle In A Graph" on LeetCode can be solved using Breadth-First Search (BFS) on a graph.

The problem statement is: Given an undirected graph, return the length of the shortest cycle that can be formed within the graph. If no cycle exists, return -1.

Algorithm:

1. Initialize a variable "cycle_length" to -1.
2. For each node in the graph, perform BFS starting from that node.
3. During the BFS, maintain a set of visited nodes, a queue of nodes to visit next, and a parent of each node.
4. If we encounter a node that is already visited and it is not the parent of the current node, we have found a cycle. Calculate the length of the cycle and update the "cycle_length" variable.
5. Continue BFS until all nodes have been visited.
6. Return the "cycle_length" variable.

Code:

Here is the Python code that implements the above algorithm:

from collections import deque

class Solution:
    def shortestCycle(self, graph: List[List[int]]) -> int:
        n = len(graph)
        cycle_length = -1
        
        # Perform BFS from each node
        for i in range(n):
            visited = set()
            q = deque()
            q.append((i, 0))
            visited.add(i)
            
            while q:
                node, level = q.popleft()
                for nei in graph[node]:
                    if nei not in visited:
                        visited.add(nei)
                        q.append((nei, level+1))
                    elif nei != node:
                        # Cycle found
                        cycle_len = level+1
                        if cycle_length == -1:
                            cycle_length = cycle_len
                        else:
                            cycle_length = min(cycle_length, cycle_len)
        
        return cycle_length

Time Complexity: O(V*(V+E)), where V is the number of vertices and E is the number of edges in the graph.

Space Complexity: O(V+E), where V is the number of vertices and E is the number of edges in the graph.

1