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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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

1from collections import defaultdict, deque
2from math import inf
3from typing import List
4
5class Solution:
6    def findShortestCycle(self, num_nodes: int, edges: List[List[int]]) -> int:
7        # Local function to perform breadth-first search (BFS) starting from a node.
8        def bfs(start_node: int) -> int:
9            distances = [-1] * num_nodes
10            distances[start_node] = 0
11            queue = deque([(start_node, -1)])
12            shortest_cycle = inf
13          
14            while queue:
15                current_node, parent_node = queue.popleft()
16              
17                # Check all adjacent nodes to the current node.
18                for adjacent in graph[current_node]:
19                    # If the adjacent node has not been visited.
20                    if distances[adjacent] == -1:
21                        distances[adjacent] = distances[current_node] + 1
22                        queue.append((adjacent, current_node))
23                    # If the adjacent node has been visited and is not the parent,
24                    # we found a cycle.
25                    elif adjacent != parent_node:
26                        shortest_cycle = min(shortest_cycle, distances[current_node] + distances[adjacent] + 1)
27          
28            return shortest_cycle
29
30        # Construct the graph as an adjacency list.
31        graph = defaultdict(list)
32        for u, v in edges:
33            graph[u].append(v)
34            graph[v].append(u)
35      
36        # Apply BFS from each node to find the shortest cycle in the graph.
37        shortest_cycle_overall = min(bfs(i) for i in range(num_nodes))
38      
39        # Return the length of the shortest cycle, or -1 if there is no cycle.
40        return shortest_cycle_overall if shortest_cycle_overall < inf else -1
41
1class Solution {
2    private List<Integer>[] graph;
3    private final int INFINITY = 1 << 30; // Represents a large number as infinity.
4
5    // Finds the shortest cycle in an undirected graph.
6    public int findShortestCycle(int n, int[][] edges) {
7        // Initialize the adjacency list for the graph.
8        graph = new List[n];
9        Arrays.setAll(graph, k -> new ArrayList<>());
10        // Populate the graph with the provided edges.
11        for (int[] edge : edges) {
12            int startVertex = edge[0], endVertex = edge[1];
13            graph[startVertex].add(endVertex);
14            graph[endVertex].add(startVertex);
15        }
16      
17        int shortestCycleLength = INFINITY;
18        // Check each vertex as a starting point to find the shortest cycle.
19        for (int i = 0; i < n; ++i) {
20            shortestCycleLength = Math.min(shortestCycleLength, bfs(i));
21        }
22        // Return the length of the shortest cycle, or -1 if it doesn't exist.
23        return shortestCycleLength < INFINITY ? shortestCycleLength : -1;
24    }
25
26    // Conducts a breadth-first search to find the shortest path back to the starting node.
27    private int bfs(int startVertex) {
28        int[] distances = new int[graph.length];
29        Arrays.fill(distances, -1); // -1 signifies that a vertex has not been visited.
30        distances[startVertex] = 0; // The starting vertex has distance 0 from itself.
31        Deque<int[]> queue = new ArrayDeque<>();
32        queue.offer(new int[]{startVertex, -1}); // The second element in the array is the 'parent' vertex.
33      
34        int shortestCycle = INFINITY;
35        while (!queue.isEmpty()) {
36            int[] currentPair = queue.poll();
37            int currentVertex = currentPair[0];
38            int parentVertex = currentPair[1];
39          
40            for (int neighbor : graph[currentVertex]) {
41                if (distances[neighbor] < 0) {
42                    // If the neighbor has not been visited, set its distance and add it to the queue.
43                    distances[neighbor] = distances[currentVertex] + 1;
44                    queue.offer(new int[] {neighbor, currentVertex});
45                } else if (neighbor != parentVertex) {
46                    // If the neighbor has been visited and is not the parent, a cycle is found.
47                    shortestCycle = Math.min(shortestCycle, distances[currentVertex] + distances[neighbor] + 1);
48                }
49            }
50        }
51        return shortestCycle;
52    }
53}
54
1#include <vector>
2#include <queue>
3#include <cstring>
4using namespace std;
5
6class Solution {
7public:
8    int findShortestCycle(int n, vector<vector<int>>& edges) {
9        // Graph representation using adjacency lists.
10        vector<vector<int>> graph(n);
11        for (auto& edge : edges) {
12            int u = edge[0], v = edge[1];
13            graph[u].push_back(v);
14            graph[v].push_back(u);
15        }
16
17        // Initialize the distance to be a very large number.
18        const int INF = 1 << 30;
19
20        // Lambda function to perform Breadth-First Search (BFS).
21        auto bfs = [&](int start) -> int {
22            vector<int> dist(n, -1); // Initialize distances to -1.
23            dist[start] = 0; // Distance to the start node is 0.
24            queue<pair<int, int>> q; // Queue to manage BFS.
25            q.emplace(start, -1); // Push start node with no parent (-1).
26
27            int shortestCycle = INF; // Store the shortest cycle length.
28            while (!q.empty()) {
29                auto [current, parent] = q.front();
30                q.pop();
31
32                for (int neighbor : graph[current]) {
33                    if (dist[neighbor] < 0) {
34                        // Neighbor not visited, set distance and enqueue.
35                        dist[neighbor] = dist[current] + 1;
36                        q.emplace(neighbor, current);
37                    } else if (neighbor != parent) {
38                        // Found a cycle, not through parent node.
39                        shortestCycle = min(shortestCycle, dist[current] + dist[neighbor] + 1);
40                    }
41                }
42            }
43            return shortestCycle;
44        };
45
46        // Search for the shortest cycle starting from each node.
47        int shortestCycleOverall = INF;
48        for (int i = 0; i < n; ++i) {
49            shortestCycleOverall = min(shortestCycleOverall, bfs(i));
50        }
51
52        // If a cycle was found, return its length; otherwise return -1. 
53        return shortestCycleOverall < INF ? shortestCycleOverall : -1;
54    }
55};
56
1// Function to find the shortest cycle in an undirected graph.
2function findShortestCycle(n: number, edges: number[][]): number {
3    // Initialize graph as adjacency list.
4    const graph: number[][] = new Array(n).fill(0).map(() => []);
5  
6    // Populate graph with edges.
7    for (const [from, to] of edges) {
8        graph[from].push(to);
9        graph[to].push(from);
10    }
11
12    // Define infinity as a value much larger than any possible path.
13    const infinity = 1 << 30;
14
15    // Temporary variable to hold the shortest cycle length found.
16    let shortestCycleLength = infinity;
17
18    // Helper function to perform breadth-first search (BFS) from a starting node.
19    const breadthFirstSearch = (startNode: number): number => {
20        // Initialize distances array with -1, signifying unvisited nodes.
21        const distances: number[] = new Array(n).fill(-1);
22
23        // The distance to the start node is 0.
24        distances[startNode] = 0;
25
26        // Queue for BFS. Each element is a tuple [node, parent].
27        const queue: number[][] = [[startNode, -1]];
28
29        // Initialize the shortest cycle length found in this BFS.
30        let cycleLength = infinity;
31
32        // Process nodes in the queue.
33        while (queue.length) {
34            const [currentNode, parentNode] = queue.shift()!;
35
36            // Check all adjacent nodes.
37            for (const neighbor of graph[currentNode]) {
38                // If the neighbor is unvisited, update its distance and add to queue.
39                if (distances[neighbor] < 0) {
40                    distances[neighbor] = distances[currentNode] + 1;
41                    queue.push([neighbor, currentNode]);
42                } else if (neighbor !== parentNode) {
43                    // If the neighbor has been visited and isn't the parent,
44                    // a cycle has been detected, update the shortest cycle length.
45                    cycleLength = Math.min(cycleLength, distances[currentNode] + distances[neighbor] + 1);
46                }
47            }
48        }
49        return cycleLength;
50    };
51
52    // Iterate over all nodes to conduct BFS and update the shortest cycle length.
53    for (let i = 0; i < n; ++i) {
54        shortestCycleLength = Math.min(shortestCycleLength, breadthFirstSearch(i));
55    }
56
57    // If a cycle has been detected, return its length; otherwise, return -1.
58    return shortestCycleLength < infinity ? shortestCycleLength : -1;
59}
60

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which data structure is used in a depth first search?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄