devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

深度优先(DFS)与广度优先(BFS)附Python代码与具体应用_深度优先搜索的时间复杂度

作者：你好赵伟 | 2024-04-29 19:30:51

赞

踩

深度优先搜索的时间复杂度

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

深度优先搜索（DFS）：

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

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

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

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

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

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

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

    1. def dfs(node, visited):
    2.     if node not in visited:
    3.         visited.add(node)
    4.         # 访问节点的邻居
    5.         for neighbor in node.neighbors:
    6.             dfs(neighbor, visited)
    7.  
    8. # 定义节点类
    9. class Node:
    10.     def __init__(self, val):
    11.         self.val = val
    12.         self.neighbors = []
    13.  
    14. # 创建树的节点
    15. node1 = Node(1)
    16. node2 = Node(2)
    17. node3 = Node(3)
    18.  
    19. # 构建树的连接关系
    20. node1.neighbors.append(node2)
    21. node1.neighbors.append(node3)
    22. node2.neighbors.append(node1)
    23. node3.neighbors.append(node1)
    24.  
    25. # 初始化已访问节点集合
    26. visited = set()
    27.  
    28. # 从根节点开始进行深度优先搜索
    29. dfs(node1, visited)
    30.  
    31. print("深度优先搜索结果:", [node.val for node in visited])

迭代实现：

  1. def dfs(root):
  2.     visited = set()
  3.     stack = [root]
  4.  
  5.     while stack:
  6.         node = stack.pop()
  7.         if node not in visited:
  8.             visited.add(node)
  9.             # 访问节点的邻居
  10.             for neighbor in node.neighbors:
  11.                 if neighbor not in visited:
  12.                     stack.append(neighbor)
  13.  
  14. # 定义节点类
  15. class Node:
  16.     def __init__(self, val):
  17.         self.val = val
  18.         self.neighbors = []
  19.  
  20. # 创建树的节点
  21. node1 = Node(1)
  22. node2 = Node(2)
  23. node3 = Node(3)
  24.  
  25. # 构建树的连接关系
  26. node1.neighbors.append(node2)
  27. node1.neighbors.append(node3)
  28. node2.neighbors.append(node1)
  29. node3.neighbors.append(node1)
  30.  
  31. # 从根节点开始进行深度优先搜索
  32. dfs(node1)
  33.  
  34. 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 是树的深度。对于图，可能需要额外的空间来记录已访问的节点，空间复杂度可能更高。

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

    1. from collections import deque
    2.  
    3. def bfs(root):
    4.     visited = set()
    5.     queue = deque([root])
    6.     visited.add(root)
    7.     
    8.     while queue:
    9.         node = queue.popleft()
    10.         # 访问节点的邻居
    11.         for neighbor in node.neighbors:
    12.             if neighbor not in visited:
    13.                 visited.add(neighbor)
    14.                 queue.append(neighbor)
    15.  
    16. # 定义节点类
    17. class Node:
    18.     def __init__(self, val):
    19.         self.val = val
    20.         self.neighbors = []
    21.  
    22. # 创建树的节点
    23. node1 = Node(1)
    24. node2 = Node(2)
    25. node3 = Node(3)
    26.  
    27. # 构建树的连接关系
    28. node1.neighbors.append(node2)
    29. node1.neighbors.append(node3)
    30. node2.neighbors.append(node1)
    31. node3.neighbors.append(node1)
    32.  
    33. # 从根节点开始进行广度优先搜索
    34. bfs(node1)
    35.  
    36. print("广度优先搜索结果:", [node.val for node in visited])

    迭代实现：

    1. from collections import deque
    2.  
    3. def bfs(root):
    4.     visited = set()
    5.     queue = deque([root])
    6.     visited.add(root)
    7.     
    8.     while queue:
    9.         node = queue.popleft()
    10.         # 访问节点的邻居
    11.         for neighbor in node.neighbors:
    12.             if neighbor not in visited:
    13.                 visited.add(neighbor)
    14.                 queue.append(neighbor)
    15.  
    16. # 定义节点类
    17. class Node:
    18.     def __init__(self, val):
    19.         self.val = val
    20.         self.neighbors = []
    21.  
    22. # 创建树的节点
    23. node1 = Node(1)
    24. node2 = Node(2)
    25. node3 = Node(3)
    26.  
    27. # 构建树的连接关系
    28. node1.neighbors.append(node2)
    29. node1.neighbors.append(node3)
    30. node2.neighbors.append(node1)
    31. node3.neighbors.append(node1)
    32.  
    33. # 从根节点开始进行广度优先搜索
    34. bfs(node1)
    35.  
    36. 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 满了，以先到者为准。

  1.  
  2. initial_state = (0,0,0)
  3. capacity = (3,5,9)
  4. goal = 7
  5.  
  6. def isgoal(state):
  7.     return  goal in state
  8.  
  9. #action:1)把瓶子装满 2）把一个瓶子中的水倒到另一个瓶子中，直到一个瓶子为空或满
  10. def get_successor(state):
  11.     #用一个list来存所有successor的状态
  12.     ret =[]
  13.     arrlen = range(len(state))
  14.     #1)三种可能性
  15.     for i in arrlen :
  16.         cur =[0,0,0]
  17.         cur[i] = capacity[i]
  18.         ret.append(tuple(cur))
  19.     #2)双重循环遍历
  20.     for i in arrlen:
  21.         for j in arrlen :
  22.             #在所有source存在的,并且target不为满，避免死循环
  23.             if i != j and state[i] != 0 : 
  24.             #判断target的剩余空间，与source所拥有的空间
  25.                 num = min(state[i],(capacity[j]-state[j]))
  26.                 #创建list
  27.                 cur = list(state)
  28.                 for x in arrlen :
  29.                     if x == i:
  30.                         cur[x] = state[i]-num 
  31.                     elif x==j:
  32.                         cur[x] = state[j]+num
  33.                     else:
  34.                         cur[x] = state[x] 
  35.                 ret.append(tuple(cur))
  36.     return ret
  37.  
  38. class node:
  39.     def __init__(self,state,parent=None):
  40.         #state是个tuple
  41.         self.state = state
  42.         self.parent= parent
  43.  
  44. from collections import deque
  45. #用深度优先无法完成任务
  46. def BFS(state):
  47.     #用一个队列来存节点，规定一下，从右边进，从左边出
  48.     stack = deque()
  49.     stack.append(node(state))#DFS
  50.     while stack:
  51.         #取出栈顶元素
  52.         curnode = stack.popleft()
  53.         if isgoal(curnode.state) :
  54.             return curnode
  55.         for successor in get_successor(curnode.state):
  56.             stack.append(node(successor,curnode))
  57.     
  58.     return None
  59.  
  60. def getPath(node):
  61.     ret = []
  62.     #存状态
  63.     while node:
  64.         ret.append(node.state)
  65.         node = node.parent
  66.     ret.reverse()
  67.     return ret
  68.  
  69. node = BFS(initial_state)
  70. target = getPath(node)
  71. print(target)

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/509385
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号