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

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

引用

CSDN

1.

https://blog.csdn.net/weixin_47520540/article/details/145800093

深度优先搜索（DFS）和广度优先搜索（BFS）是两种常用的图遍历算法，用于解决图相关的问题。它们在搜索问题中具有广泛的应用，如路径搜索、连通性检测等。

图片引自：https://www.cnblogs.com/xuxinstyle/p/13261651.html

深度优先搜索（DFS）

深度优先搜索是一种先探索到尽可能深的节点，再回溯到之前的节点的搜索策略。在实现上，DFS通常使用递归或栈来实现。

模板：

def dfs(node, visited):
    if node in visited:
        return
    visited.add(node)
    # Process current node
    # Explore neighbors
    for 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 True
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            if dfs(neighbor, end, visited, graph):
                return True
    return False

广度优先搜索（BFS）

广度优先搜索是一种先探索到当前节点的所有邻居节点，再逐层向外搜索的策略。通常使用队列来实现。

模板：

from collections import deque

def 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. 重复上述步骤，直到队列为空。

分类模板：如果不需要确定当前遍历到了哪一层，模板如下

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 deque

def 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 distance
        visited.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")