DFS总结
关于标记:
- 标记的主要目的:搜索的时候不会往回走
- 取消标记:让其它路劲也可以访问该点,适用于路径不同产生的效果不同的情况
- 不取消标记:适用于每个点只需访问一遍的情况:连通性判断
关于返回值:
- 在递归出口一定要 return, 否则会错误
- 如果 dfs 返回值是 bool, 在调用 dfs 处也要返回 bool 值
关于参数:
参数用来放置搜索中会发生变化的状态
参数可以表示 dfs 深度
如果要在 dfs 出口处比较这次 选择结果的最大值或最小值,可将其放在参数上
有时为了判断dfs出口,设置一个计数器参数 (搜索所有可能的情况,选最有解) (注意dfs出口处要有return)