一个网站 二级域名,搜索排名查询,社区教育网站建设方案,网站的开发建设费深度优先搜索#xff08;DFS#xff09;和广度优先搜索#xff08;BFS#xff09;是两种常用的图遍历算法#xff0c;用于解决图相关的问题。它们在搜索问题中具有广泛的应用#xff0c;如路径搜索、连通性检测等。 以下是具体区别#xff1a; #xff08;图片引自DFS和广度优先搜索BFS是两种常用的图遍历算法用于解决图相关的问题。它们在搜索问题中具有广泛的应用如路径搜索、连通性检测等。 以下是具体区别 图片引自https://www.cnblogs.com/xuxinstyle/p/13261651.html 深度优先搜索DFS
深度优先搜索是一种先探索到尽可能深的节点再回溯到之前的节点的搜索策略。在实现上DFS通常使用递归或栈来实现。
模板
def dfs(node, visited):if node in visited:returnvisited.add(node)# Process current node# Explore neighborsfor neighbor in node.neighbors:dfs(neighbor, visited)
讲解
1. 从起始节点开始访问当前节点并标记为已访问。 2. 对当前节点的邻居节点进行遍历若邻居节点未被访问过则以该邻居节点为新的当前节点继续进行深度优先搜索。 3. 递归地进行上述步骤直到所有可达节点都被访问。
例题
问题给定一个无向图判断是否存在从节点A到节点B的路径。
def hasPath(graph, start, end):判断是否存在从start到end的路径Args:graph: 图的邻接表表示start: 起始节点end: 目标节点Returns:bool: 如果存在路径返回True否则返回Falsevisited set()return dfs(start, end, visited, graph)def dfs(node, end, visited, graph):深度优先搜索的辅助函数Args:node: 当前节点end: 目标节点visited: 已访问过的节点集合graph: 图的邻接表表示Returns:bool: 如果存在路径返回True否则返回Falseif node end:return Truevisited.add(node)for neighbor in graph[node]:if neighbor not in visited:if dfs(neighbor, end, visited, graph):return Truereturn False 广度优先搜索BFS
广度优先搜索是一种先探索到当前节点的所有邻居节点再逐层向外搜索的策略。通常使用队列来实现。把每个还没有搜索到的点依次放入队列然后再弹出队列的头部元素当做当前遍历点。模板
from collections import dequedef bfs(start):广度优先搜索Args:start: 起始节点Returns:Nonequeue deque([start])visited set()while queue:node queue.popleft()if node not in visited:visited.add(node)# Process current node# 处理当前节点# Explore neighbors# 探索当前节点的邻居节点for neighbor in node.neighbors:queue.append(neighbor) 要点
1. 将起始节点加入队列并标记为已访问。 2. 当队列不为空时弹出队首节点对其未被访问的邻居节点进行遍历。 3. 将未被访问的邻居节点加入队列并标记为已访问。 4. 重复上述步骤直到队列为空。 分类模板如果不需要确定当前遍历到了哪一层模板如下这里参考https://www.cnblogs.com/xuxinstyle/p/13261651.html
while queue 不空cur queue.pop()for 节点 in cur的所有相邻节点if 该节点有效且未访问过queue.push(该节点)
如果要确定当前遍历到了哪一层BFS模板如下 这里增加了level表示当前遍历到二叉树中的哪一层了也可以理解为在一个图中现在已经走了多少步了。size表示在当前遍历层有多少个元素也就是队列中的元素数我们把这些元素一次性遍历完即把当前层的所有元素都向外走了一步。
level 0
while queue 不空size queue.size()while (size --) {cur queue.pop()for 节点 in cur的所有相邻节点if 该节点有效且未被访问过queue.push(该节点)}level ;
例题
问题给定一个无向图从节点A开始找到到节点B的最短路径的长度。
from collections import dequedef shortestPath(graph, start, end):寻找从start到end的最短路径长度Args:graph: 图的邻接表表示start: 起始节点end: 目标节点Returns:int: 最短路径长度如果不存在路径则返回-1queue deque([(start, 0)])visited set()while queue:node, distance queue.popleft()if node end:return distancevisited.add(node)for neighbor in graph[node]:if neighbor not in visited:queue.append((neighbor, distance 1))return -1 # If no path found# Example graph representation: {node: [neighbors]}
graph {A: [B, C],B: [A, D, E],C: [A, F],D: [B],E: [B, F],F: [C, E]
}print(shortestPath(graph, A, F)) # Output: 2
这里使用了BFS算法来搜索从节点A到节点B的最短路径的长度。
下面是代码的一些区别这里使用字典来存图
BFS实现
#BFS实现
graph {A:[B,C],B:[A,C,D],C:[A,B,D,F],D:[B,C,E,F],E:[C,D],F:[D]}
def BFS(graph,s):queue []queue.append(s)#将元素 s 加入到队列的尾部队尾seen set()#储存出现过的量seen.add(s)while(len(queue)0):vertex queue.pop(0)#从队列的头部队首弹出元素nodes graph[vertex]#vertex的所有临接点for w in nodes:if w not in seen:queue.append(w)seen.add(w)print(vertex)
BFS(graph,A)
DFS实现 队列—栈
graph {A:[B,C],B:[A,C,D],C:[A,B,D,F],D:[B,C,E,F],E:[C,D],F:[D]}
def BFS(graph,s):queue []queue.append(s)seen set()#储存出现过的量seen.add(s)while(len(queue)0):vertex queue.pop()#pop(0)-pop() 先弹出最后一个元素 这里体现出栈nodes graph[vertex]#vertex的所有临接点for w in nodes:if w not in seen:queue.append(w)seen.add(w)print(vertex)BFS(graph,A)
