BFS(广度优先搜索)算法在未连接且无向图中的运行时间复杂度为O(V+E),其中V为图中顶点的数量,E为图中边的数量。
下面是一个使用Python实现BFS算法的示例代码:
from collections import deque
def bfs(graph, start):
visited = set() # 用于存储已访问的节点
queue = deque() # 用于广度优先搜索的队列
queue.append(start)
visited.add(start)
while queue:
node = queue.popleft() # 取出队列中的首个节点
print(node, end=' ')
neighbors = graph[node] # 获取当前节点的邻居节点
for neighbor in neighbors:
if neighbor not in visited:
queue.append(neighbor) # 将未访问的邻居节点加入队列
visited.add(neighbor) # 将邻居节点标记为已访问
# 创建一个未连接且无向图的邻接表表示
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# 从顶点A开始进行广度优先搜索
bfs(graph, 'A')
以上代码中,我们使用了一个集合(visited)来记录已访问的节点,一个双端队列(queue)来实现广度优先搜索。通过在队列中不断添加未访问的邻居节点,并在每次循环时取出队列中的首个节点进行访问,即可实现BFS算法。
由于每个节点最多被访问一次,而每个边也最多被访问一次,所以BFS算法的时间复杂度为O(V+E)。