การค้นหาตามแนวกว้าง (BFS) ใน Python
ในบทเรียนนี้ คุณจะท่องกราฟทีละระดับด้วยการค้นหาตามแนวกว้างและคิว deque
บทนำ
ปัญหาที่ต้องแก้
ต้องใช้กี่ขั้นในการไปจากคนหนึ่งถึงอีกคนในเครือข่ายสังคม หรือจากช่องหนึ่งของเขาวงกตไปยังทางออก breadth-first search สำรวจเป็นวงตามระยะทาง ครั้งแรกที่มันไปถึง node หนึ่งจึงเป็นตามเส้นทางที่สั้นที่สุด
ลองนึกภาพแบบนี้
breadth-first search เหมือนระลอกคลื่นบนสระน้ำ โยนก้อนหินลงที่จุดเริ่ม และระลอกคลื่นไปถึงทุกอย่างที่ห่างหนึ่งขั้นก่อน แล้วทุกอย่างที่ห่างสองขั้น ไปเรื่อยๆ ไม่มีอะไรที่ไกลกว่าถูกแตะก่อนที่ทุกอย่างที่ใกล้กว่าจะถูกไปถึง
queue = deque(["A"])🪨 โยนก้อนหินลงที่ Anode = queue.popleft()🌊 หยิบ node ถัดไปตามลำดับระยะทางif neighbor not in visited:🔎 ยังไม่ได้ไปถึงใช่ไหม?queue.append(neighbor)➕ เพิ่มเข้าวงถัดไปbreadth-first search (BFS) ไปที่ทุก node ของกราฟทีละระดับจาก node เริ่มต้นโดยใช้คิว จึงหาเส้นทางที่สั้นที่สุดในกราฟที่ไม่มีน้ำหนักได้
ประเด็นสำคัญ
queueเก็บ node ที่รอการสำรวจ โดยตัวที่เก่าที่สุดมาก่อนvisitedบันทึก node ที่เจอแล้ว ไม่มีตัวไหนถูกเพิ่มสองครั้ง และวงจรจึงวนไม่รู้จบไม่ได้node = queue.popleft()หยิบ node ถัดไป และเพื่อนบ้านที่ยังไม่ได้ไปของมันต่อท้ายคิวorderแสดง A แล้วเพื่อนบ้านของมันคือ B และ C แล้ว D และ E ที่ไกลออกไปอีกหนึ่งระดับ
ใช้เมื่อไร?
- เส้นทางที่สั้นที่สุดในกราฟที่ไม่มีน้ำหนัก ตาราง และเขาวงกต
- ระดับความห่างในเครือข่ายสังคม
- web crawler และการหาทุกอย่างที่ไปถึงได้จากจุดเริ่มต้น
เมื่อไรยังไม่จำเป็น
- เส้นเชื่อมมีต้นทุนต่างกัน เช่น ระยะทางถนน: ใช้อัลกอริทึมของ Dijkstra
- คุณต้องสำรวจเส้นทางหนึ่งให้สุดก่อนเส้นอื่น เช่น สำหรับ backtracking: ใช้ depth-first search
ภาพจำลอง การค้นหาตามแนวกว้าง (BFS) ใน Python
O(V + E)กด เล่น หรือ ทีละขั้น เพื่อดูการเปรียบเทียบและการย้ายข้อมูลแต่ละขั้น
โค้ดตัวอย่าง
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']
อธิบายโค้ด
คิว queue เก็บโหนดที่รอการเยี่ยม และส่งออกตามลำดับที่เข้ามา เซต visited จำโหนดที่เจอแล้ว เพื่อไม่ให้เยี่ยมโหนดเดิมซ้ำเมื่อกราฟมีวงรอบ ลำดับการเยี่ยมคือ A, B, C, D, E และความซับซ้อนคือ O(V + E) โดย V คือจำนวนโหนดและ E คือจำนวนเส้นเชื่อม
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัดเพิ่มเติม
ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก
- ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
- จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
ข้อผิดพลาดที่พบบ่อย
ทำเครื่องหมายว่าไปแล้วช้าเกินไป
ถ้า node ถูกทำเครื่องหมายแค่ตอนหยิบออกจากคิว มันอาจถูกเพิ่มหลายครั้ง
node = queue.popleft()
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
เรียนบทนี้จบแล้วใช่ไหม
ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า
ฝึกด้วยโจทย์
ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI
- Can We Split Into Two Teams? Decide whether people can be assigned to two teams so that each listed pair is on opposite teams. ปานกลาง
- Tree Diameter A tree is a connected undirected graph with no cycles. ปานกลาง
- Count Islands Count groups of connected land cells in a grid. ปานกลาง