Solution: Shortest Cycle in a Graph
Explore how to detect the shortest cycle in an undirected graph by applying Breadth-First Search (BFS). Understand how BFS traversal helps identify cycles and calculate their lengths, allowing you to determine the minimal cycle length or confirm no cycles exist. This lesson guides you through algorithm design, adjacency list construction, BFS implementation, and complexity analysis for efficient graph cycle detection.
We'll cover the following...
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:
n...