是不是没法通过BFS推算回cycle_path了
来源：5-6 使用 BFS 求解环检测问题
慕粉2011219583
2020-02-18
好像没法通过pre来倒推回环路了
【测试用例】
顶点数: 7, 边数: 6
0: 1 2
1: 0 3 4
2: 0 3 6
3: 1 2
4: 1
5:
6: 2
【遍历顺序】
v: 0 出列
–w: 1 未访问，入列
–w: 2 未访问，入列
v: 1 出列
–w: 0 已访问，v: 1，v[pre]: 0，不符合要求
–w: 3 未访问，入列
–w: 4 未访问，入列
v: 2 出列
–w: 0 已访问，v: 2，v[pre]: 0，不符合要求
–w: 3 已访问，v: 2，v[pre]: 0，!= w，符合要求
----w: 3 已找到环
此时：pre = [0, 0, 0, 1, 1, -1, -1]
通过pre[3]倒推，然后死循环了
写回答
1回答
-
是的，如果要寻找环具体是怎样的，不能使用 BFS：）
继续加油！：）
112020-02-18
相似问题