深度优先搜索，拼音：shēn dù yōu xiān sōu suǒ
英语：深度优先； 深度FS
学科：计算机科学与技术_理论计算机科学_数据结构
相关名词：图、树、回溯、递归、堆栈
从图中指定的顶点V开始，首先访问V，然后选择与顶点V相邻且未被访问过的顶点W，然后从W开始，用同样的方法访问W的未访问过的相邻点。 直到图中所有与顶点V相连的顶点都被访问过。
深度优先搜索
深度优先搜索是一种遍历或搜索树或图的算法。 该算法尽可能深地搜索树的分支。 当节点 v 的边都被探索完后，搜索将回溯到找到节点 v 的边的起始节点。
深度优先搜索的实现可以分为两个主要步骤：
1. 探索：访问从给定起始顶点可到达的所有顶点。
2.回溯：当通过路径访问完所有顶点后，搜索算法开始“回溯”，从当前顶点开始沿着每条未探索的边，重复第一步。
以下是深度优先搜索的基本实现过程：
1. 从根节点开始查找。
2. 如果当前节点是目标节点，则结束搜索。
3. 否则，探索所有未探索的相邻节点。
4、如果所有相邻节点都已被探索过，则回溯到当前节点的父节点，继续探索父节点未探索过的相邻节点。
5. 重复步骤3-4，直到找到目标节点或回溯到根节点。
深度优先搜索的时间复杂度取决于图的结构和实现。 在最坏的情况下，如果图是完全图，则时间复杂度为 O(n!)，其中 n 是顶点数。 然而，对于一般图，时间复杂度通常为 O(n+m)，其中 n 是顶点数，m 是边数。
深度优先搜索 (DFS) 中的回溯发生在探索了从当前节点可到达的所有相邻节点之后。 回溯就是将搜索过程从当前节点移至其父节点并继续搜索过程。
以下是深度优先搜索中回溯的基本实现步骤：
1.当所有相邻节点都被探索完后，程序将从当前节点回溯到父节点。
2、在回溯过程中，需要记录每个节点，以便如果有尚未探索的相邻节点，可以从该节点继续搜索。
3、重复这个过程，直到到达根节点或者找到目标节点。
确切的实现可能会根据编程语言和具体问题的不同而有所不同，但基本思想是相同的。 通常，我们使用堆栈来协助深度优先搜索和回溯。 当我们探索一个新节点时，我们将其推入堆栈。 当我们完成搜索节点并需要回溯到其父节点时，我们将节点从堆栈中弹出。
下面是一个简单的示例代码，演示了深度优先搜索和回溯的基本实现：
def dfs（图，开始）：
堆栈=[开始]
= 设置（）
而堆栈：
= 堆栈.pop()
如果不在：
。添加（）
stack.(graph[] - ) # 将未访问的相邻节点压入栈
在此示例中，我们使用字典来表示图，其中每个键是一个顶点，每个值是与该顶点相邻的一组顶点。 我们使用堆栈来保存要访问的顶点，并使用集合来跟踪已访问的顶点。 当我们访问一个顶点时，我们将其所有未访问的相邻节点压入堆栈。 当堆栈为空时，我们已经访问了从起始顶点可到达的所有顶点，算法结束。
