BFS สำรวจกราฟทีละระดับ โดยเยี่ยมชมเพื่อนบ้านทั้งหมดของโหนดก่อนที่จะเดินไปลึก ใช้ คิว และค้นหา เส้นทางที่สั้นที่สุด (ขอบน้อยที่สุด) ในกราฟที่ไม่มีน้ำหนัก
แนวคิด
เริ่มต้นที่แหล่งที่มา ใส่ลงในคิว จากนั้นทำซ้ำโดยนำโหนดออกจากคิว เยี่ยมชมเพื่อนบ้านที่ยังไม่เยี่ยมชม และใส่พวกเขาลงในคิว ชุด visited ป้องกันการเยี่ยมชมซ้ำ
ตัวอย่าง
collections deque
():
visited = {start}
queue = deque([start])
order = []
queue:
node = queue.popleft()
order.append(node)
nbr graph[node]:
nbr visited:
visited.add(nbr)
queue.append(nbr)
order
graph = {: [, ], : [], : [], : []}
bfs(graph, )
