小工具知识网

当前位置: 首页 > 行业知识 > 深度优先(DFS)与广度优先(BFS)附Python代码与具体应用

行业知识

深度优先(DFS)与广度优先(BFS)附Python代码与具体应用

2026-11-20 22:40:09 来源:互联网转载

���度优先搜索(DFS)和广度优先搜索(BFS)是两种常用的图搜索算法,用于在图或树等数据结构中查找特定节点或遍历整个结构。它们在解决许多问题时都非常有用,包括路径查找、连通性检测和图形遍历等。

()

深度优先搜索(DFS):

  • 工作原理: 在深度优先搜索中,我们从起始节点开始沿着一条路径尽可能深地探索,直到到达最远的节点,然后返回并探索其他的分支。换句话说,DFS 会尽可能深地搜索当前路径,直到没有更多的未探索节点为止。

  • 算法实现: 通常使用递归或栈来实现 DFS。递归的方法将在堆栈中维护当前路径,而非递归方法则需要使用显式的栈数据结构来跟踪节点。

    ()
  • 特点: DFS 通常需要较少的内存空间,因为它只需要存储当前路径上的节点。但它可能会陷入无限循环,特别是在图中存在环路时。

  • 应用: DFS 适用于寻找一条路径、深度优先遍历树或图,以及解决具有递归结构的问题。

  • 时间复杂度: 在最坏情况下,DFS 需要遍历整个搜索空间,其时间复杂度取决于节点数量和边的数量。对于树来说,时间复杂度通常为 O(b^d) ,其中 b是每一层平均节点的数量,d 是树的层数。

  • 空间复杂度: 在 DFS 中,需要存储当前路径上的节点,因此空间复杂度取决于树的深度。在最坏情况下,当搜索到树的最大深度时,空间复杂度为 O(bd)迭代或者O(d)递归,b是平均节点数目,其中 d 是树的深度((b-1)*d)->bd)。对于图,由于可能存在环路,空间复杂度可能更高,取决于搜索过程中所访问的节点数量。

  • 以下是递归实现的实例代码:

    def dfs(node, visited):    if node not in visited:        visited.add(node)        # 访问节点的邻居        for neighbor in node.neighbors:            dfs(neighbor, visited)# 定义节点类class Node:    def __init__(self, val):        self.val = val        self.neighbors = []# 创建树的节点node1 = Node(1)node2 = Node(2)node3 = Node(3)# 构建树的连接关系node1.neighbors.append(node2)node1.neighbors.append(node3)node2.neighbors.append(node1)node3.neighbors.append(node1)# 初始化已访问节点集合visited = set()# 从根节点开始进行深度优先搜索dfs(node1, visited)print("深度优先搜索结果:", [node.val for node in visited])

    迭代实现:

    def dfs(root):    visited = set()    stack = [root]    while stack:        node = stack.pop()        if node not in visited:            visited.add(node)            # 访问节点的邻居            for neighbor in node.neighbors:                if neighbor not in visited:                    stack.append(neighbor)# 定义节点类class Node:    def __init__(self, val):        self.val = val        self.neighbors = []# 创建树的节点node1 = Node(1)node2 = Node(2)node3 = Node(3)# 构建树的连接关系node1.neighbors.append(node2)node1.neighbors.append(node3)node2.neighbors.append(node1)node3.neighbors.append(node1)# 从根节点开始进行深度优先搜索dfs(node1)print("深度优先搜索结果:", [node.val for node in visited])

    广度优先搜索(BFS):

    • 工作原理: 在广度优先搜索中,我们从起始节点开始,逐层地探索图中的节点,先探索距离起始节点最近的节点,然后是稍远一层的节点,依次类推。换句话说,BFS 会首先探索所有与起始节点相邻的节点,然后再探索这些节点的邻居,以此类推。

    • 算法实现: BFS 通常使用队列来实现。它将从起始节点开始,将节点入队,并逐个将节点的邻居出队并入队,直到队列为空。

    • 特点: BFS 保证可以找到最短路径,因为它会先探索距离起始节点更近的节点。但它可能会占用较多的内存空间,特别是在图结构较大的情况下。

    • 应用: BFS 适用于寻找最短路径、查找最短路径、层次遍历树或图,以及解决具有固定距离或层次结构的问题。

    • 时间复杂度: 在最坏情况下,BFS 需要遍历整个搜索空间,因此其时间复杂度与节点数量和边的数量成正比。对于树或图来说, O(b^d) ,其中 b是每一层平均节点的数量,d 是树的层数。

    • 空间复杂度: 在 BFS 中,需要存储每一层的节点,并且需要将每个节点的子节点添加到队列中。在最坏情况下,如果树是满的,则每一层将包含平均 b 个节点,其中 b 是每个节点的子节点数量。因此,BFS 的空间复杂度为 O(b^d)(当前层的长度),其中 d 是树的深度。对于图,可能需要额外的空间来记录已访问的节点,空间复杂度可能更高。

    • 以下是递归实现的实例代码:

      from collections import dequedef bfs(root):    visited = set()    queue = deque([root])    visited.add(root)        while queue:        node = queue.popleft()        # 访问节点的邻居        for neighbor in node.neighbors:            if neighbor not in visited:                visited.add(neighbor)                queue.append(neighbor)# 定义节点类class Node:    def __init__(self, val):        self.val = val        self.neighbors = []# 创建树的节点node1 = Node(1)node2 = Node(2)node3 = Node(3)# 构建树的连接关系node1.neighbors.append(node2)node1.neighbors.append(node3)node2.neighbors.append(node1)node3.neighbors.append(node1)# 从根节点开始进行广度优先搜索bfs(node1)print("广度优先搜索结果:", [node.val for node in visited])

      迭代实现:

      from collections import dequedef bfs(root):    visited = set()    queue = deque([root])    visited.add(root)        while queue:        node = queue.popleft()        # 访问节点的邻居        for neighbor in node.neighbors:            if neighbor not in visited:                visited.add(neighbor)                queue.append(neighbor)# 定义节点类class Node:    def __init__(self, val):        self.val = val        self.neighbors = []# 创建树的节点node1 = Node(1)node2 = Node(2)node3 = Node(3)# 构建树的连接关系node1.neighbors.append(node2)node1.neighbors.append(node3)node2.neighbors.append(node1)node3.neighbors.append(node1)# 从根节点开始进行广度优先搜索bfs(node1)print("广度优先搜索结果:", [node.val for node in visited])

      当我们谈论树搜索算法时,常常会涉及到两个重要的概念:完全性(Completeness)和最优性(Optimality)。

      完全性(Completeness):

      • 完全性指的是算法是否能够保证在有限时间内找到解决方案。一个完全的搜索算法能够在有限时间内找到解(如果解存在的话)。在树搜索中,完全性意味着算法能够遍历整个搜索空间并找到解决方案。

      • 深度优先搜索(DFS)在完全性上的表现: DFS 并不保证完全性。尽管 DFS 可能会找到解决方案,但它可能会陷入无限循环,尤其是当搜索空间有环路时。因此,DFS 不是一个完全的搜索算法。

      • 广度优先搜索(BFS)在完全性上的表现: BFS 是一种完全的搜索算法。由于 BFS 会逐层地遍历整个搜索空间,因此如果解决方案存在,则 BFS 能够找到该解决方案。

        最优性(Optimality):

        • 最优性指的是算法是否能够找到最佳的解决方案。一个最优的搜索算法能够找到满足特定标准的最佳解决方案。在树搜索中,通常是指找到成本最小的解决方案。

        • 深度优先搜索(DFS)在最优性上的表现: DFS 不能保证找到最优解,因为它可能会首先遍历到解决方案,但这个解决方案可能不是最优的。因为 DFS 会尽可能地深入搜索路径,而不考虑路径的成本。

        • 广度优先搜索(BFS)在最优性上的表现: BFS 是一种最优的搜索算法,因为它会首先找到最短路径,也就是成本最低的解决方案。由于 BFS 会先探索距离起始节点最近的节点,因此如果成本一样,它会优先找到最短路径。

          实际案例:

          在一个倒水问题中,你被给定一组水壶,每个水壶都有一个容量(以升为单位)和当前的水位(以升为单位)。目标是测量出一定量的水,它可以出现在任何一个水壶中。假设我们有三个水壶,一个容量为 5 升,另一个容量为 3 升,另一个容量为 9 升。我们的目标是测量出 7 升水。一个状态由当前水位的元组表示,可用的操作包括:

          (填满,i):将第 i 个水壶全部装满(来自一个无限水源)。 (倒水,i,j):将水从第 i 个水壶倒入第 j 个水壶,直到水壶 i 为空,或者水壶 j 满了,以先到者为准。

          initial_state = (0,0,0)capacity = (3,5,9)goal = 7def isgoal(state):    return  goal in state#action:1)把瓶子装满 2)把一个瓶子中的水倒到另一个瓶子中,直到一个瓶子为空或满def get_successor(state):    #用一个list来存所有successor的状态    ret =[]    arrlen = range(len(state))    #1)三种可能性    for i in arrlen :        cur =[0,0,0]        cur[i] = capacity[i]        ret.append(tuple(cur))    #2)双重循环遍历    for i in arrlen:        for j in arrlen :            #在所有source存在的,并且target不为满,避免***循环            if i != j and state[i] != 0 :             #判断target的剩余空间,与source所拥有的空间                num = min(state[i],(capacity[j]-state[j]))                #创建list                cur = list(state)                for x in arrlen :                    if x == i:                        cur[x] = state[i]-num                     elif x==j:                        cur[x] = state[j]+num                    else:                        cur[x] = state[x]                 ret.append(tuple(cur))    return retclass node:    def __init__(self,state,parent=None):        #state是个tuple        self.state = state        self.parent= parentfrom collections import deque#用深度优先无法完成任务def BFS(state):    #用一个队列来存节点,规定一下,从右边进,从左边出    stack = deque()    stack.append(node(state))#DFS    while stack:        #取出栈顶元素        curnode = stack.popleft()        if isgoal(curnode.state) :            return curnode        for successor in get_successor(curnode.state):            stack.append(node(successor,curnode))        return Nonedef getPath(node):    ret = []    #存状态    while node:        ret.append(node.state)        node = node.parent    ret.reverse()    return retnode = BFS(initial_state)target = getPath(node)print(target)

上一篇:优盘文件丢失如何恢复?

下一篇:HTML登录成功后跳转策略揭秘,打造流畅用户体验的秘诀!