深度优先搜索——不撞南墙不回头

【资料图】

配套视频：深度优先搜索——不撞南墙不回头

主要思想：

深度优先搜索,又称DFS，是一种常用的图搜索算法，常用于解决图的遍历、路径查找、连通性判断等问题。它以深度为优先级，不断深入地探索图中的节点，直到达到最大深度或无法进一步探索为止。它是一种递归算法，基本思想是：从图中的某个节点出发，沿着一条路径尽可能深入地搜索，直到达到最深处或无法继续搜索为止，然后回溯到前一节点，再沿着另一条路径进行深入搜索。当所有节点都被访问完毕时，算法结束。深度优先搜索的关键就在于标记已访问的节点以避免重复访问。常用的标记方式是使用一个Bool数组，将每个节点对应的位置设为已访问。

深度优先查找正诠释了什么叫“不撞南墙不回头”。

适用范围：

有关于图的问题。

例题：

例1

例2

总结：

总结一下，今天我们聊了聊【深度优先搜索】，它是一种简单而强大的图搜索算法。它通过递归实现，以深度为优先级进行节点遍历，能够解决许多图相关的问题。

在具体实现该算法时，可以选择使用递归。递归函数在进入每一层时都会进行访问标记，回溯时再取消标记。

好啦，关于深度优先搜索就说到这里。这里是康郭聊算法，拜拜！

#注：例题答案请查看视频。