2608. Shortest Cycle in a Graph

Problem Description

In this problem, we're given a bi-directional graph with n vertices, labeled from 0 to n - 1. The edges between these vertices are provided in the form of a 2D integer array edges, where each sub-array has two integers representing an edge between the vertices it contains. The graph described does not allow for multiple edges between the same pair of vertices and does not allow for an edge to connect a vertex to itself.

We are asked to return the length of the shortest cycle within the graph. In graph theory, a cycle is a path that begins and ends at the same vertex and traverses each edge only once. If no such cycle exists, we should return -1. This is a classic graph search problem that could involve techniques such as depth-first search (DFS) or breadth-first search (BFS).

Intuition

To find the shortest cycle, we need a way to traverse the graph and keep track of the distances from a starting node. The natural choice here is BFS, which allows us to explore the graph level by level, starting at a particular vertex.

We use BFS starting at each vertex and find the shortest path that returns to the starting vertex, thus creating a cycle. By maintaining an array of distances, we can check for the existence of a cycle whenever we visit a vertex that we have seen before, provided we didn't reach it by going back the way we came from (i.e., not backtracking).

For every vertex, we perform BFS and keep track of:

• The distance from the starting vertex to every other vertex we visit.
• The predicessor of each visited vertex to ensure we do not consider backtracking as part of a cycle.

When we discover a vertex that has been visited already (and is not the predecessor), we've found a cycle. We can calculate the cycle's length by summing up the distances (from the starting point to the current vertex and from the starting point to the visited vertex) and add 1 (for the edge that closes the cycle).

We repeat this process for each vertex in the graph and keep track of the minimum cycle length found. If we find no cycles at all after performing BFS from every vertex, we return -1.

The provided solution leverages the BFS method combined with the idea of checking for cycles without backtracking to ensure the shortest path is calculated.

Learn more about Breadth-First Search and Graph patterns.

Solution Approach

To implement the solution, we're using two main approaches, each making use of Breadth-First Search (BFS) and adjacency lists to represent the graph. An adjacency list g is a dictionary where each vertex key maps to a list of adjacent vertices, making it efficient to iterate over neighbours.

Solution 1: Enumerate edges + BFS

This approach constructs the adjacency list g for representing the graph using the edges array. With this adjacency graph, we can perform BFS from each vertex, looking for the shortest path to any other vertex.

For each vertex u, we launch a BFS that computes the shortest distance to other vertices. During this search, if we find a vertex v that we've seen before, and it's not the vertex we came from (not the parent, labeled fa in the code), then we've discovered a cycle. We calculate the cycle's length as dist[u] + dist[v] + 1, taking into account the distance of both vertices from the starting point and adding one for the edge that completes the cycle.

We execute this process for all possible edges, looking for the shortest cycle. If we find cycles, we return the length of the shortest one; otherwise, we return -1.

Solution 2: Enumerate points + BFS

In the second approach, similar to the first, we also build the adjacency list g. However, instead of enumerating the edges, we visit every vertex u and perform BFS to look for cycles initiated from that vertex.

During the BFS, for each visited vertex v, we check if there is another path to v that doesn't go through the immediate parent (not backtracking). If such a path exists, we've found a cycle. The length of the cycle is then given by adding the distances of the two intersecting paths to v, indicating the cycle's perimeter.

If, by going through all vertices, at least one cycle is found, we return the length of the shortest cycle found. Otherwise, our return value is -1.

Data Structures and Patterns:

• bfs(u: int) -> int: A helper function for BFS, which takes a starting vertex u and returns the length of the shortest cycle found when starting from u.
• defaultdict(list): To dynamically create the adjacency list without checking whether a vertex key already exists.
• deque: A double-ended queue from the collections module used to efficiently pop vertices from the front of the queue while performing BFS.
• dist = [-1] * n: An array that keeps track of distances to vertices from the starting vertex; initialized to -1 for vertices that haven't been visited.
• inf: To initialize the minimum cycle length to infinity, so any cycle found will update this to a smaller value as cycles are detected.

Overall, the algorithms and data structures chosen here are tailored for efficiency and clarity when finding the shortest cycle in an undirected graph. The time complexity for Solution 1 is O(m^2) and Solution 2 is also O(m^2) (where m is the number of edges, and n is the number of vertices), because they both involve running BFS, which in the worst case examines all vertices and edges. The space complexity is O(m + n) to accommodate the adjacency list and additional data structures used in the algorithms.

Example Walkthrough

Let's consider a small bi-directional graph with 5 vertices (0 through 4) and 6 edges. The edges array is given as follows:

1edges = [[0, 1], [0, 2], [1, 2], [1, 3], [2, 3], [3, 4]]

Step 1: Build the Adjacency List

We would build an adjacency list from the given edges:

1g = {
2  0: [1, 2],
3  1: [0, 2, 3],
4  2: [0, 1, 3],
5  3: [1, 2, 4],
6  4: [3]
7}

Step 2: Initialize Variables and Data Structures

Before we start BFS, we define:

• dist array to keep track of distances ([-1] * n where n = 5).
• minCycle variable to keep track of the shortest cycle found, initialized with inf.

Step 3: BFS from Each Vertex

Perform BFS from each vertex. Let's illustrate a BFS starting at vertex 0.

We enqueue the starting vertex (0, -1) (vertex, parent) to a queue. Here, -1 means that the starting vertex has no parent.

BFS Iteration 1:

• We dequeue (0, -1) and mark dist[0] = 0.
• We enqueue its neighbors (1, 0) and (2, 0) with distances dist[1] = 1 and dist[2] = 1.

BFS Iteration 2:

• Dequeue (1, 0). Enqueue neighbors (2, 1) and (3, 1) with distances dist[2] = 2 and dist[3] = 2.
• As we visit node 2, we find that 2 is already visited and 2 is not the parent of 1. Thus, we have found a cycle with nodes (0, 1, 2). The length of this cycle is dist[0] + dist[2] + 1 = 0 + 2 + 1 = 3.

BFS from Other Vertices:

We repeat the above process starting from each of the other vertices (1, 2, 3, 4). Let's say we find no shorter cycle than length 3. Then 3 would be the answer.

Step 4: Return Shortest Cycle Length

If we find cycles, return the length of the shortest cycle found; otherwise, return -1. In this case, we found a cycle of length 3, so the function returns 3.

This illustrative example uses the same steps outlined earlier in the Solution Approach section, implementing the BFS algorithm to search for the shortest cycle by traversing the graph from each vertex. The dist array helps ensure we are finding the shortest non-backtracking path, and the minCycle variable updates with the smallest cycle length as we proceed.

Solution Implementation

Time and Space Complexity

The provided code defines a class Solution with a method findShortestCycle that computes the shortest cycle in an undirected graph represented by its number of vertices n and edges edges.

Time Complexity

The time complexity of the method findShortestCycle primarily depends on the breadth-first search (BFS) operation performed inside the bfs local function.

For each vertex i in the range 0 to n-1, we perform a BFS:

• In the worst case, the BFS from a single vertex visits all n vertices and considers all m edges in the graph. This happens because we have to check each edge to find any possible cycles, which translates to a complexity of O(m).
• Since we perform this BFS for each of the n vertices, the overall time complexity is O(n * m).

Thus, the total time complexity of findShortestCycle is O(n * m).

Space Complexity

The space complexity consists of the storage used by:

• The adjacency list g, which contains an entry for each vertex. Each entry has a list of adjacent vertices. In the worst case, if the graph is fully connected, this would take O(n + m) space, as each edge contributes to two vertex lists.
• The dist array, which is of length n and stores distances from the start vertex for BFS.
• The BFS queue q, which in the worst case can contain all vertices, inducing an O(n) space requirement.

Adding these contributions together, the space complexity is O(m + n) for the adjacency list and O(n) for both dist array and the queue, leading to a total space complexity being O(n + m).

To summarize, the space complexity of the findShortestCycle method is O(m + n).

Learn more about how to find time and space complexity quickly using problem constraints.