Python实战开发及案例分析（20）—— 宽度优先

05-13 1041阅读

宽度优先搜索（Breadth-First Search, BFS）是一种遍历图或树的算法。它从根节点开始，探索所有邻近节点，然后再按顺序访问每个邻近节点的邻居，直到所有节点都被访问为止。在图中，为了避免访问同一个节点多次，通常使用一个队列来记录已经访问过但其邻居节点还未完全探索的节点。

（图片来源网络，侵删）

BFS的基本步骤：

初始化：将起始节点放入队列中。
循环执行以下操作，直到队列为空：
- 从队列中取出一个节点。
- 访问该节点的所有未访问的邻近节点，将它们加入队列中，并标记为已访问。

Python实现

下面是使用Python实现BFS的一个示例，我们将使用一个简单的无向图来演示。

图的定义

我们将使用字典来表示图，其中键是节点，值是与键节点直接相连的节点列表。

graph = {
    'A' : ['B','C'],
    'B' : ['D', 'E'],
    'C' : ['F'],
    'D' : [],
    'E' : ['F'],
    'F' : []
}

BFS 实现

我们将定义一个函数来执行BFS，并打印出访问的节点顺序。

from collections import deque
def bfs(graph, start):
    visited = set()  # 创建一个集合，用于存储已访问的节点
    queue = deque([start])  # 创建一个队列，初始化为包含起始节点的队列
    
    while queue:
        vertex = queue.popleft()  # 从队列中取出一个节点
        if vertex not in visited:
            visited.add(vertex)  # 标记为已访问
            print(vertex, end=" ")  # 打印节点
            # 将所有未访问的邻接节点添加到队列中
            queue.extend([node for node in graph[vertex] if node not in visited])
# 调用函数
bfs(graph, 'A')

输出应该是：A B C D E F，这表示了访问的顺序。

案例分析：社交网络

假设我们有一个社交网络，我们需要找出从一个人到另一个人通过朋友的最短路径。在这个场景中，BFS非常适合用来解决这个问题，因为它总是优先扩展距离根节点最近的节点。

社交网络图

social_graph = {
    'Alice' : ['Bob', 'Cindy', 'Joe'],
    'Bob' : ['Alice', 'Eve'],
    'Cindy' : ['Alice', 'Eve'],
    'Joe' : ['Alice'],
    'Eve' : ['Bob', 'Cindy']
}

找出最短路径

我们可以修改bfs函数来跟踪节点的父节点，以便可以重建最短路径。

def bfs_shortest_path(graph, start, goal):
    visited = set()
    queue = deque([(start, [start])])  # 队列中存储节点及路径
    
    while queue:
        (vertex, path) = queue.popleft()
        for next in set(graph[vertex]) - visited:
            if next == goal:
                return path + [next]
            else:
                visited.add(next)
                queue.append((next, path + [next]))
# 调用函数查找最短路径
path = bfs_shortest_path(social_graph, 'Alice', 'Eve')
print("Shortest path:", path)

输出将是：Shortest path: ['Alice', 'Eve']，展示了从Alice到Eve的最短路径。

通过这种方式，宽度优先搜索不仅可以帮助我们遍历图或树，还能解决诸如最短路径问题等更复杂的问题，这在各种网络分析和图算法中非常有用。

继续探索宽度优先搜索（BFS）的应用，我们可以将其扩展到更多复杂和实用的场景中，如组件连接性、解决迷宫问题、以及在多层网络结构中的应用。这些进阶使用案例进一步展示了BFS的多样性和功能强大的侧面。

应用场景扩展

1. 组件连接性检查

在图论中，BFS可用于检查图中是否存在从一个节点到另一个节点的路径，以及图是否连通（在无向图中）。这在网络设计和分析中尤为重要。

实例：检查图中的连通性

def is_connected(graph, start_node):
    visited = set()
    queue = deque([start_node])
    
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            queue.extend([neighbor for neighbor in graph[node] if neighbor not in visited])
    
    # 如果访问的节点数等于图中的节点数，则图是连通的
    return len(visited) == len(graph)
# 测试连通性
print("Is the graph connected?", is_connected(graph, 'A'))

这段代码能够判断从给定起点出发的图是否完全连通。

2. 解决迷宫问题

BFS是解决迷宫问题的经典方法，尤其适合找到从起点到终点的最短路径。

实例：迷宫的最短路径

def solve_maze(maze, start, end):
    rows, cols = len(maze), len(maze[0])
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]  # 下，右，上，左
    queue = deque([(start, [start])])
    
    while queue:
        (x, y), path = queue.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0

VPS购买请点击我