无向图的广度优先搜索算法

算法介绍

广度优先搜索（Breadth-First Search，简称 BFS）是一种用于遍历或搜索树或图的算法。它从根节点开始，逐层向四周扩散，访问所有相邻节点，然后依次处理每一层中的节点。在无向图中应用该算法可以找到任意两个节点间的最短路径。

算法原理

BFS 通常使用一个队列来存储待访问的节点，并维护一个集合或数组记录已访问过的节点。遍历过程如下：

1. 初始化：将起始节点加入队列，标记该节点为已访问。
2. 循环处理：
   • 如果队列为空，则搜索结束。
   • 从队列中取出一个节点进行处理（如打印其值或记录相关信息）。
   • 将此节点的所有未被访问的邻接节点加入队列，并标记这些节点为已访问。

算法步骤

1. 初始化：选择一个起始节点，创建一个空的队列并将该节点入队。同时创建一个集合或数组用于记录所有已访问过的节点。
2. 广度优先遍历：
   • 当队列不为空时，进行以下操作：
     1. 取出队首元素，并处理这个节点（例如打印、记录等）。
     2. 将该节点的所有未被访问过的邻接节点加入队列，并标记为已访问。
3. 结束：当队列为空时，遍历结束。

示例代码

以下是使用 Python 实现的广度优先搜索算法：

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        if node not in visited:
            print(f'Visit: {node}')
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)

# 示例图
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 从节点 A 开始进行广度优先搜索
bfs(graph, 'A')

复杂度分析

• 时间复杂度：在最坏情况下，每个节点和每条边都会被访问一次，因此时间复杂度为 O(V + E)，其中 V 表示顶点数，E 表示边数。
• 空间复杂度：需要一个队列存储待处理的顶点，大小最多为 V 个；还需要一个集合或数组记录已访问过的顶点。因此空间复杂度同样为 O(V)。

应用场景

广度优先搜索算法在许多实际问题中非常有用，如社交网络中的好友推荐、最短路径查找等场景都有其应用价值。

通过上述介绍和示例代码，可以了解如何实现并应用无向图的广度优先搜索算法。