行业知识
深度优先(DFS)与广度优先(BFS)附Python代码与具体应用
���度优先搜索(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)
-
-
-