有向图环检查回溯中对onPath值的回溯的疑问

来源：13-3 有向图环检测和 DAG

甲骨文_0001

2022-01-01

图片描述
老师，问题如上，然后图中是我自己的理解，之所以老师在课程中在检测出环的时候(即return true)的时候之所以没有对onPath[v]回溯，我理解是因为既然检查到环了，任务就好了，至于是不是要对onPath[v]=false不重要了，只有在对v所有邻边结点都检查完都没发现一个环的时候才有必要对onPath[v]=false作这个回溯操作。
我自己想既然从一个源点假定源点0到其它点，那么最终递归一路结束会返回到源点0，那么只要保持住visited数组的值就好了，而onPath数组我会在递归结束后进行清理即回溯，最终函数整个运行完成即退出对源点0的递归后，onPath数组里面的所有元素都会复原回false。老师，我说的是对的吗：）
今天是2022年第一天，祝老师元旦快乐哈~~~~~~~~:)

写回答

1回答

liuyubobobo

2022-01-01

抱歉，我没有特别理解你的意思。你的意思是说 onPath 你觉得不需要？还是代码需要怎么改？还是这个代码你觉得没问题，只是描述了一下自己的理解？

新年快乐！：）

liuyubobobo

甲骨文_0001

明白了，没有问题的。因为我们的目标是找到环，一旦找到以后，我的代码就放弃维护 onPath 了。但如果你选择继续维护 onPath，保证最终退出整个递归的时候，onPath 全部为 false，是没问题的，整个算法的复杂度也不会改变。我印象里你之前对另外一个递归代码提过类似的问题，其实是一样的意思：）继续加油！：）

2022-01-01

共2条回复

玩转算法系列--图论精讲（Java版）

30+小时系统学习，bobo带你克服被图论支配的恐惧

1591 学习 · 324 问题

查看课程

相似问题

回溯

回答 1

波波老师，dfs中的回溯算法是不是自带的就有回溯的

回答 1

并查集能不能找到有向图的环

回答 1

Hamliton回路求解回溯pre数组也需要像visited数组一样回溯

回答 1

波波老师您好，这是我用DFS你讲的第一种方法做的欧拉回路，请帮忙看下对不对？

回答 1

打开慕课网App查看更多内容