• 【Python搜索算法】广度优先搜索（BFS）算法原理详解与应用，示例+代码

    目录

    1 广度优先搜索    

    2 应用示例

    2.1 迷宫路径搜索

    2.2 社交网络中的关系度排序

    2.3 查找连通区域

    1 广度优先搜索    

            广度优先搜索（Breadth-First Search，BFS）是一种图遍历算法，用于系统地遍历或搜索图（或树）中的所有节点。BFS的核心思想是从起始节点开始，首先访问其所有相邻节点，然后逐层向外扩展，逐一访问相邻节点的相邻节点，以此类推。这意味着BFS会优先探索距离起始节点最近的节点，然后再逐渐扩展到距离更远的节点。BFS通常用于查找最短路径、解决迷宫问题、检测图是否连通以及广泛的图问题。

    BFS算法的步骤如下：

    1. 初始化：选择一个起始节点，将其标记为已访问，并将其放入队列中（作为起始节点）。

    2. 进入循环：重复以下步骤，直到队列为空。 a. 从队列中取出一个节点。 b. 访问该节点。 c. 将所有未访问的相邻节点加入队列。 d. 标记已访问的节点，以避免重复访问。

    3. 结束循环：当队列为空时，表示已经遍历完整个图。

    以下是BFS的算法原理详解和一个应用示例：

    算法原理：

            BFS的工作原理是通过队列数据结构来管理待访问的节点。它从起始节点开始，然后逐一访问该节点的相邻节点，并将它们加入队列。然后，它从队列中取出下一个节点进行访问，以此类推。这确保了节点按照它们的距离从起始节点逐层遍历，因此BFS可以用于查找最短路径。

            BFS是一个宽度优先的搜索，它在查找最短路径等问题中非常有用。它不会陷入深度过深的路径，因为它会优先探索距离起始节点更近的节点。

    2 应用示例

    2.1 迷宫路径搜索

            假设有一个迷宫，其中包含墙壁和通道，您希望找到从起始点到终点的最短路径。BFS是解决这类问题的理想选择。

    示例迷宫：

    1. S 0 0 1 1 1
    2. 1 1 0 1 0 1
    3. 1 0 0 0 0 1
    4. 1 1 1 1 0 1
    5. 1 0 0 1 0 1
    6. 1 1 1 1 1 E
    • S 表示起始点
    • E 表示终点
    • 0 表示可以通过的通道
    • 1 表示墙壁

     使用BFS，您可以找到从起始点到终点的最短路径，如下所示：

    1. 从起始点 S 开始，将其加入队列。
    2. 逐层遍历节点，首先访问距离 S 最近的节点。
    3. 在每一步中，将所有可以通过的相邻节点加入队列，同时标记已访问的节点。
    4. 继续这个过程，直到到达终点 E。

    BFS会优先探索距离 S 最近的通道，因此它会找到从 S 到 E 的最短路径。在上面的迷宫中，BFS将找到一条最短路径，经过标有数字 0 的通道，最终到达终点 E。这是BFS在寻找最短路径问题中的一个实际应用示例。

    示例：

    1. import matplotlib.pyplot as plt
    2. from collections import deque
    3.  
    4.  
    5. def bfs_shortest_path(maze, start, end):
    6.     # 定义四个方向移动的偏移量，分别是上、下、左、右
    7.     directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    8.     rows, cols = len(maze), len(maze[0])
    9.  
    10.     # 创建队列用于BFS
    11.     queue = deque([(start, [start])])
    12.     visited = set()
    13.  
    14.     while queue:
    15.         (x, y), path = queue.popleft()
    16.         visited.add((x, y))
    17.  
    18.         if (x, y) == end:
    19.             return path  # 找到了最短路径
    20.  
    21.         for dx, dy in directions:
    22.             new_x, new_y = x + dx, y + dy
    23.  
    24.             if 0 <= new_x < rows and 0 <= new_y < cols and maze[new_x][new_y] == 0 and (new_x, new_y) not in visited:
    25.                 new_path = path + [(new_x, new_y)]
    26.                 queue.append(((new_x, new_y), new_path))
    27.  
    28.     return None  # 没有找到路径
    29.  
    30. def draw_maze(maze, path=None):
    31.     rows, cols = len(maze), len(maze[0])
    32.  
    33.     # 创建一个图形对象
    34.     fig, ax = plt.subplots()
    35.  
    36.     # 绘制迷宫
    37.     for x in range(rows):
    38.         for y in range(cols):
    39.             if maze[x][y] == 0:
    40.                 ax.add_patch(plt.Rectangle((y, -x - 1), 1, 1, facecolor="white"))
    41.             else:
    42.                 ax.add_patch(plt.Rectangle((y, -x - 1), 1, 1, facecolor="gray"))
    43.  
    44.     # 绘制路径（如果存在）
    45.     if path:
    46.         for x, y in path:
    47.             ax.add_patch(plt.Rectangle((y, -x - 1), 1, 1, facecolor="green"))
    48.  
    49.     # 设置坐标轴
    50.     ax.set_aspect("equal")
    51.     ax.set_xticks(range(cols))
    52.     ax.set_yticks(range(-rows, 0))
    53.     ax.set_xticklabels([])
    54.     ax.set_yticklabels([])
    55.  
    56.     plt.grid(True)
    57.     plt.show()
    58.  
    59.  
    60. # 示例迷宫，0表示通道，1表示墙壁
    61. maze = [
    62.     [0, 0, 0, 1, 1, 1],
    63.     [1, 1, 0, 1, 0, 1],
    64.     [1, 0, 0, 0, 0, 1],
    65.     [1, 1, 1, 1, 0, 1],
    66.     [1, 0, 0, 1, 0, 0],
    67.     [1, 1, 0, 0, 1, 0]
    68. ]
    69.  
    70. start = (0, 0)  # 起始点
    71. end = (5, 5)  # 终点
    72.  
    73. path = bfs_shortest_path(maze, start, end)
    74.  
    75. draw_maze(maze, path)

    2.2 社交网络中的关系度排序

            广度优先搜索（BFS）的排序应用示例之一是使用它在无权图中查找最短路径。在前面的示例中，我们已经展示了如何使用BFS查找迷宫中的最短路径。这是BFS的一个典型应用示例。

            另一个排序应用示例是社交网络中的关系度排序。在社交网络中，您可以使用BFS来确定您与其他用户之间的关系度，即您与其他用户之间的最短路径，或者共同的朋友数量。以下是一个简单的示例：

            假设您有一个社交网络，其中用户之间的关系用图表示，其中节点代表用户，边代表用户之间的关系。您想知道您与其他用户之间的关系度，并按关系度对用户进行排序。

    1. import networkx as nx
    2. import matplotlib.pyplot as plt
    3. from collections import deque
    4.  
    5. # 创建一个复杂的社交网络图
    6. social_network = {
    7.     'You': ['Alice', 'Bob', 'Claire', 'David'],
    8.     'Alice': ['Diana', 'Eva', 'Frank'],
    9.     'Bob': ['Eva', 'Frank', 'George'],
    10.     'Claire': ['Diana', 'George', 'Hannah'],
    11.     'David': ['Hannah'],
    12.     'Diana': ['Eva', 'George'],
    13.     'Eva': ['Frank'],
    14.     'Frank': ['George', 'Hannah'],
    15.     'George': ['Hannah'],
    16.     'Hannah': [],
    17. }
    18.  
    19. def bfs_relationship_degree(graph, start):
    20.     visited = set()
    21.     queue = deque([(start, 0)])  # 用于存储节点和关系度
    22.  
    23.     relationship_degree = {}  # 存储关系度
    24.  
    25.     while queue:
    26.         node, degree = queue.popleft()
    27.  
    28.         if node not in visited:
    29.             visited.add(node)
    30.             relationship_degree[node] = degree
    31.  
    32.             for friend in graph[node]:
    33.                 if friend not in visited:
    34.                     queue.append((friend, degree + 1))
    35.  
    36.     return relationship_degree
    37.  
    38. # 使用BFS查找关系度
    39. your_name = 'You'
    40. relationship_degree = bfs_relationship_degree(social_network, your_name)
    41.  
    42. # 创建一个有向图
    43. G = nx.DiGraph()
    44.  
    45. # 添加节点和边
    46. for user, degree in relationship_degree.items():
    47.     G.add_node(user, degree=degree)
    48.  
    49. for user in social_network:
    50.     for friend in social_network[user]:
    51.         G.add_edge(user, friend)
    52.  
    53. # 绘制图形
    54. pos = nx.spring_layout(G, seed=42)
    55. labels = nx.get_node_attributes(G, 'degree')
    56. nx.draw(G, pos, with_labels=True, node_size=1000, node_color='lightblue', font_size=10, font_color='black')
    57. nx.draw_networkx_labels(G, pos, labels, font_size=10, font_color='black')
    58. plt.title("复杂社交网络图")
    59. plt.show()
    60.  
    61. # 输出排序结果
    62. sorted_users = sorted(relationship_degree.items(), key=lambda x: x[1])
    63. for user, degree in sorted_users:
    64.     print(f'{user}: 关系度 {degree}')

    输出：

     输出：

    1. You: 关系度 0
    2. Alice: 关系度 1
    3. Bob: 关系度 1
    4. Claire: 关系度 1
    5. David: 关系度 1
    6. Diana: 关系度 2
    7. Eva: 关系度 2
    8. Frank: 关系度 2
    9. George: 关系度 2
    10. Hannah: 关系度 2

     这段代码的目的是使用广度优先搜索（BFS）算法来查找社交网络中您（'You'）与其他用户之间的关系度，并绘制社交网络图。

    1. 首先，定义了一个复杂的社交网络图，其中包括不同用户之间的关系。这个社交网络图存储在 social_network 字典中。

    2. bfs_relationship_degree 函数实现了BFS算法来查找您与其他用户之间的关系度。它从您开始，逐层查找与您相连接的用户，计算它们之间的关系度。结果存储在 relationship_degree 字典中。

    3. 创建一个有向图（DiGraph） G 以绘制社交网络图。

    4. 添加节点和边到图 G，其中节点代表用户，边代表用户之间的关系。此时，节点的颜色和大小被设置为 lightblue 和 1000，并且边的颜色为 gray。

    5. 使用 NetworkX 提供的布局算法 spring_layout 来确定节点的位置。

    6. 绘制图形，包括节点和边，以及节点上的标签。

    7. 输出用户的关系度排序结果，按照从您（'You'）到其他用户的关系度进行排序。

    运行该代码将绘制出社交网络图，并输出用户的关系度排序结果。这可以帮助您可视化您与其他用户之间的关系，并查看谁与您更亲近。

    2.3 查找连通区域

            在图像处理中，连通区域是由相邻像素组成的区域，具有相似的特性（如颜色或灰度）。BFS可以用来查找和标记这些连通区域。

    1. import cv2
    2. import numpy as np
    3.  
    4. # 读取图像
    5. image = cv2.imread('img.jpg', 0)  # 以灰度模式读取图像
    6. ret, binary_image = cv2.threshold(image, 127, 255, cv2.THRESH_BINARY)
    7.  
    8. # 创建一个与图像大小相同的标记图
    9. height, width = binary_image.shape
    10. markers = np.zeros((height, width), dtype=np.int32)
    11.  
    12. # 定义一个颜色映射
    13. color_map = {
    14.     1: (0, 0, 255),  # 红色
    15.     2: (0, 255, 0),  # 绿色
    16.     3: (255, 0, 0),  # 蓝色
    17.     4: (0, 255, 255),  # 黄色
    18.     # 您可以根据需要添加更多颜色
    19. }
    20.  
    21. # 连通区域计数
    22. region_count = 0
    23.  
    24. # 定义8个邻域的偏移
    25. neighbor_offsets = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
    26.  
    27. # 开始查找连通区域
    28. for y in range(height):
    29.     for x in range(width):
    30.         if binary_image[y, x] == 255 and markers[y, x] == 0:
    31.             region_count += 1
    32.             markers[y, x] = region_count
    33.             queue = [(y, x)]
    34.  
    35.             while queue:
    36.                 current_y, current_x = queue.pop(0)
    37.  
    38.                 for dy, dx in neighbor_offsets:
    39.                     ny, nx = current_y + dy, current_x + dx
    40.  
    41.                     if 0 <= ny < height and 0 <= nx < width and binary_image[ny, nx] == 255 and markers[ny, nx] == 0:
    42.                         markers[ny, nx] = region_count
    43.                         queue.append((ny, nx))
    44.  
    45. # 将连通区域标记为不同颜色
    46. result_image = np.zeros((height, width, 3), dtype=np.uint8)
    47. for y in range(height):
    48.     for x in range(width):
    49.         if markers[y, x] > 0:
    50.             result_image[y, x] = color_map[markers[y, x]]
    51.  
    52. # 显示结果图像
    53. cv2.imshow('Connected Components', result_image)
    54. cv2.waitKey(0)
    55. cv2.destroyAllWindows()

             这段代码首先读取了一个灰度图像（也可以使用彩色图像），将其转换为二值图像。然后，它使用BFS算法查找连通区域，对不同的连通区域进行标记，并将它们标记为不同的颜色。最后，它显示带有标记的结果图像。

  • 相关阅读:
    Kubernetes二进制部署——理论部分
    检测域名是否支持http2.0协议脚本
    参加了个算法比赛，真是一言难尽啊
    buuctf PWN warmup_csaw_2016
    Kotlin中布尔类型、字符类型、字符串类型和数组类型
    Vue中自定义实现类似el-table的表格效果实现行颜色根据数据去变化展示
    深入理解 Java 对象的内存布局
    python容器之列表(list)
    Git --》如何玩转Gitee？
    【Java+SpringBoot】监考任务分配系统（源码+远程部署+项目定制开发+代码讲解+毕业设计+答辩教学）
  • 原文地址：https://blog.csdn.net/qq_35831906/article/details/133859867