#2608

Hard

auto_awesomeGraph traversal with breadth-first search

LeetCode Problem Workspace

Shortest Cycle in a Graph

Find the shortest cycle in a bi-directional graph using BFS for optimal traversal.

Problem Statement

You are given a bi-directional graph with n vertices, each labeled from 0 to n-1. The graph's edges are represented by a 2D integer array edges, where each element [ui, vi] indicates an edge between vertices ui and vi. Each vertex pair has at most one edge, and there are no self-loops or repeated edges.

Your task is to find 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, with each edge used exactly once.

Examples

Example 1

Input: n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]

Output: 3

The cycle with the smallest length is : 0 -> 1 -> 2 -> 0

Example 2

Input: n = 4, edges = [[0,1],[0,2]]

Output: -1

There are no cycles in this graph.

Constraints

2 <= n <= 1000
1 <= edges.length <= 1000
edges[i].length == 2
0 <= ui, vi < n
ui != vi
There are no repeated edges.

Solution Approach

Breadth-First Search (BFS)

To detect the shortest cycle, we perform a BFS starting from each node. During the traversal, if we encounter a node that has already been visited, it indicates a cycle. We then calculate the length of the cycle and update the minimum length found.

Cycle Detection

While performing BFS, we need to keep track of the parent node to avoid counting the immediate back-edge as part of a cycle. A cycle is only valid if it connects back to a node already visited, excluding the parent node.

Optimization Considerations

The algorithm iterates over all nodes, applying BFS. Each BFS run takes O(n + m) time, where n is the number of nodes and m is the number of edges. The complexity can be optimized by terminating early when the shortest cycle is found.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the BFS approach is O(n * (n + m)) since we start BFS from each node, where n is the number of vertices and m is the number of edges. The space complexity is O(n + m) due to the need to store the graph and visited nodes during BFS traversal.

What Interviewers Usually Probe

Look for a solution that applies BFS to effectively detect cycles in graphs.
Assess the candidate's understanding of BFS traversal and cycle detection logic.
Check if the candidate optimizes the algorithm to stop early when the shortest cycle is found.

Common Pitfalls or Variants

Common pitfalls

Forgetting to track the parent node during BFS traversal, leading to false cycle detections.
Failing to account for disconnected components, which can result in missed cycles.
Overcomplicating the cycle detection logic, leading to unnecessary additional operations.

Follow-up variants

Graph with directed edges.
Undirected graphs with weighted edges.
Graphs with more than one cycle.

FAQ

How can BFS be used to detect cycles in a graph?

BFS can be used to detect cycles by keeping track of visited nodes and ensuring we don't revisit the parent node. If a node is revisited that's not the parent, a cycle is detected.

What is the time complexity of the Shortest Cycle in a Graph problem?

The time complexity is O(n * (n + m)), where n is the number of nodes and m is the number of edges in the graph.

How can we improve the performance of this solution?

You can optimize the solution by stopping the BFS as soon as the shortest cycle is found, thus reducing the number of unnecessary traversals.

Are there any other methods to solve this problem?

While BFS is the most straightforward method, other graph traversal algorithms like DFS or even Floyd-Warshall could be used, but they may not be as efficient for cycle detection.

What should we do if the graph has no cycles?

If the graph has no cycles, simply return -1, indicating no cycle exists.

terminal

Solution

Solution 1: Enumerate edges + BFS

We first construct the adjacency list $g$ of the graph according to the array $edges$, where $g[u]$ represents all the adjacent vertices of vertex $u$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:
        def bfs(u: int, v: int) -> int:
            dist = [inf] * n
            dist[u] = 0
            q = deque([u])
            while q:
                i = q.popleft()
                for j in g[i]:
                    if (i, j) != (u, v) and (j, i) != (u, v) and dist[j] == inf:
                        dist[j] = dist[i] + 1
                        q.append(j)
            return dist[v] + 1

        g = defaultdict(set)
        for u, v in edges:
            g[u].add(v)
            g[v].add(u)
        ans = min(bfs(u, v) for u, v in edges)
        return ans if ans < inf else -1

Solution 2: Enumerate points + BFS

Similar to Solution 1, we first construct the adjacency list $g$ of the graph according to the array $edges$, where $g[u]$ represents all the adjacent vertices of vertex $u$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:
        def bfs(u: int, v: int) -> int:
            dist = [inf] * n
            dist[u] = 0
            q = deque([u])
            while q:
                i = q.popleft()
                for j in g[i]:
                    if (i, j) != (u, v) and (j, i) != (u, v) and dist[j] == inf:
                        dist[j] = dist[i] + 1
                        q.append(j)
            return dist[v] + 1

        g = defaultdict(set)
        for u, v in edges:
            g[u].add(v)
            g[v].add(u)
        ans = min(bfs(u, v) for u, v in edges)
        return ans if ans < inf else -1

Continue Practicing

#2577 minimum time to visit a cell in a grid #2685 count the number of complete components #2493 divide nodes into the maximum number of groups