【Algorithm】回溯法与深度优先遍历的异同

时间:2024-08-17 21:37:38

1、相同点:

回溯法在实现上也是遵循深度优先的,即一步一步往前探索,而不像广度优先那样,由近及远一片一片地扫。

2、不同点

(1)访问序

深度优先遍历:

  目的是“遍历”,本质是无序的。也就是说访问次序不重要,重要的是都被访问过了。

可以参见题Surrounded Regions,深度优先只需要把从边界起始的'O'全部访问到即可。

因此在实现上,只需要对于每个位置记录是否被visited就足够了。

回溯法:

  目的是“求解过程”,本质是有序的。也就是说必须每一步都是要求的次序。

可以参见题Word Search,需要以要求的序进行深度优先探索,必须每一步都符合要求。

因此在实现上,不能使用visited记录,因为同样的内容不同的序访问就会造成不同的结果,而不是仅仅“是否被访问过”这么简单。

要使用访问状态来记录,也就是对于每个点记录已经访问过的邻居方向,回溯之后从新的未访问过的方向去访问邻居。

至于这点点之前有没有被访问过并不重要,重要的是没有以当前的序进行访问。

(2)访问次数

深度优先遍历:已经访问过的节点不再访问,所有点仅访问一次。

回溯法:已经访问过的点可能再次访问,也可能存在没有被访问过的点。