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.

#2608

Hard

auto_awesome图·搜索

LeetCode 题解工作台

图中的最短环

现有一个含 n 个顶点的双向图，每个顶点按从 0 到 n - 1 标记。图中的边由二维整数数组 edges 表示，其中 edges[i] = [u i , v i ] 表示顶点 u i 和 v i 之间存在一条边。每对顶点最多通过一条边连接，并且不存在与自身相连的顶点。返回图中最短环的长度…

广度优先搜索图

题目描述

现有一个含 n 个顶点的双向图，每个顶点按从 0 到 n - 1 标记。图中的边由二维整数数组 edges 表示，其中 edges[i] = [u_i, v_i] 表示顶点 u_i 和 v_i 之间存在一条边。每对顶点最多通过一条边连接，并且不存在与自身相连的顶点。

返回图中最短环的长度。如果不存在环，则返回 -1 。

环是指以同一节点开始和结束，并且路径中的每条边仅使用一次。

示例 1：

输入：n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]
输出：3
解释：长度最小的循环是：0 -> 1 -> 2 -> 0

示例 2：

输入：n = 4, edges = [[0,1],[0,2]]
输出：-1
解释：图中不存在循环

提示：

2 <= n <= 1000
1 <= edges.length <= 1000
edges[i].length == 2
0 <= u_i, v_i < n
u_i != v_i
不存在重复的边

lightbulb

解题思路

方法一：枚举删除的边 + BFS

我们先根据数组 $edges$ 构建出邻接表 $g$ ，其中 $g[u]$ 表示顶点 $u$ 的所有邻接点。

接下来，我们枚举双向边 $(u, v)$ ，如果删除该边后，从顶点 $u$ 到顶点 $v$ 的路径依然存在，则包含该边的最短环的长度为 $dist[v] + 1$ ，其中 $dist[v]$ 表示从顶点 $u$ 到顶点 $v$ 的最短路径长度。我们取所有这样的环的最小值即可。

时间复杂度 $O(m^2)$ ，空间复杂度 $O(m + n)$ 。其中 $m$ 和 $n$ 分别为数组 $edges$ 的长度以及顶点数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2577 在网格图中访问一个格子的最少时间 #2685 统计完全连通分量的数量 #2493 将节点分成尽可能多的组