BFS算法时间复杂度是O(V+E),其中V为顶点数,E为边数。下面给出一个使用BFS算法查找图中最短路径的示例代码:
from queue import Queue
def bfs(graph, start, end):
visited = set() # 记录已经访问过的顶点
q = Queue() # 用队列来保存需要遍历的顶点
q.put(start) # 把起始顶点加入队列
visited.add(start)
while not q.empty():
node = q.get() # 取出队首顶点
if node == end:
return True # 找到最短路径
for neighbor in graph[node]: # 遍历与该顶点相邻的顶点
if neighbor not in visited:
q.put(neighbor) # 将该顶点加入队列
visited.add(neighbor)
return False # 没有找到最短路径
该代码可以在O(V+E)的时间复杂度内找到两个顶点之间的最短路径。