BFS 和 DFS（深度优先搜索、广度优先搜索）

深度优先搜索（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，否则返回False"""visited = set()return dfs(start, end, visited, graph)def dfs(node, end, visited, graph):"""深度优先搜索的辅助函数Args:node: 当前节点end: 目标节点visited: 已访问过的节点集合graph: 图的邻接表表示Returns:bool: 如果存在路径返回True，否则返回False"""if 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:None"""queue = 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: 最短路径长度，如果不存在路径则返回-1"""queue = 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")