Solution: Shortest Cycle in a Graph

Statement

You are given a bidirectional graph with n vertices, labeled from 0 to n - 1. The graph is represented by a 2D integer array edges, where each element edges[i] = [ui, vi] represents an edge connecting vertex ui and vertex vi. Each vertex pair has at most one edge between them, and no vertex is connected to itself.

Your task is to find the length of the shortest cycle in the graph. A cycle is defined as a path that starts and ends at the same vertex, with each edge in the path appearing exactly once. If no cycle exists in the graph, return -1.

Constraints:  

• $2 \leq$ n $\leq 1000$

• $1 \leq$ edges.length $\leq 1000$

• edges.length $== 2$

• $0 \leq$ ui, vi $<$ n  

• ui $\neq$ vi

• No duplicate edges exist in the graph

Solution

The goal is to find the shortest cycle in an undirected graph, that is, the smallest loop where we can start at one node and return to it without repeating any edges. To achieve this, we use Breadth-First Search (BFS), which is effective for finding the shortest path in unweighted graphs. If, during this search, we reach a node that has already been visited (but isn’t the direct parent of the current node), it indicates a cycle. This way, BFS helps us efficiently detect cycles and calculate their lengths.

The BFS begins from each unvisited node in the graph. It explores all nodes at the same distance from the starting point before going deeper into the graph. It first visits all nodes that are one edge away from the starting point, then nodes two edges away, and so on. This layer-by-layer exploration helps detect the shortest cycle early, because cycles found sooner are smaller in length.

During this traversal, the algorithm keeps track of visited nodes and their distances from the starting node. If it revisits a node that isn’t the direct parent of the current node, a cycle is detected. The length of the cycle can then be calculated based on the distance between the starting point and the end node of a path. By repeating this process for each unvisited node, we determine the shortest cycle in the entire graph. If at least one cycle is found, we return the length of the shortest one. Otherwise, we return -1 to indicate the graph has no cycles.

Let’s look at the algorithm steps:

1. Create an adjacency list representation of the graph using the given edges. This allows fast and easy access to each node’s neighbors.

2. Define the helper function, bfs(graph, start, visited), that does the following:

   1. Initializes a dist list to keep track of the distance of each node from the starting node, start, using -1 to represent unvisited nodes.

   2. Uses a queue for BFS traversal. Each item in the queue stores a tuple of the current node and its parent node.

   3. Marks the start node as visited by setting its distance to 0.

   4. Initializes a variable minCycle to track the shortest cycle found during this BFS traversal.

   5. While the queue is not empty:

      1. Dequeue the front node and get its current distance.

      2. For each neighbor of the current node:

         1. Skip the neighbor if it’s the parent node to avoid trivial backtracking.

         2. If the neighbor has already been visited (its distance is not -1), a cycle is detected. Compute its length and update minCycle if it’s shorter.

         3. If the neighbor has not been visited, mark its distance and enqueue it for further traversal.

   6. After BFS completes, return the shortest cycle length found from this start node, or Integer.MAX_VALUE if no cycle is found.

3. Traverse each node in the graph:

   1. Use a visited list initialized with -1 to keep track of which nodes have been explored.

   2. For each node i, if it hasn’t been visited yet, run the bfs function from that node.

   3. After each BFS call, compare the returned cycle length with the global result and update it if a shorter cycle is found.

4. If result is still Integer.MAX_VALUE, it means no cycles were found in the graph, return -1. Otherwise, return the smallest cycle length found.

The slides below help to understand the solution in a better way.