การค้นหาแนวกว้าง BFS ใน Python
BFS ใช้ queue เพื่อเยี่ยม neighbor ที่ใกล้ก่อน
การค้นหาแนวกว้าง BFS ใน Python คืออะไร?
BFS ใช้ queue เพื่อเยี่ยม neighbor ที่ใกล้ก่อน
สำรวจ graph ทีละระดับ
ควรใช้เมื่อใด?
- ทำความเข้าใจอัลกอริทึมและโครงสร้างข้อมูล
- สังเกตแต่ละขั้นตอนและกรณีขอบ
- เปรียบเทียบเวลาและหน่วยความจำ
ภาพจำลอง การค้นหาแนวกว้าง BFS ใน Python
O(V+E)กด เล่น หรือ ทีละขั้น เพื่อดูการเปรียบเทียบและการย้ายข้อมูลแต่ละขั้น
โค้ดตัวอย่าง
main.py
from collections import deque
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
queue = deque(["A"])
visited = {"A"}
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
print(order)ผลลัพธ์ที่คาดหวัง
['A', 'B', 'C', 'D', 'E']หลักการทำงาน
visited ป้องกันการเยี่ยมซ้ำ ใช้เวลา O(V+E) และหน่วยความจำ O(V)
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัด
ลองเปลี่ยน input และทดสอบกรณีขอบก่อนใช้ชุดข้อมูลที่ใหญ่ขึ้น
- ทดสอบ input ว่าง หนึ่งสมาชิก และค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นตอน
- เปรียบเทียบประสิทธิภาพกับวิธีอื่น