Solution: Shortest Cycle in a Graph

Explore how to use Breadth-First Search to detect and find the shortest cycle in an undirected graph. This lesson guides you through building an adjacency list, performing BFS from each node, and identifying cycles efficiently. By the end, you'll understand how to determine the shortest cycle length or confirm if none exist, applying these concepts to graph-related coding interview problems.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

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] = [u_i, v_i] represents an edge connecting vertex u_i and vertex v_i. 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:

...