อัลกอริทึม Python

การค้นหาตามแนวกว้าง (BFS) ใน Python

ในบทเรียนนี้ คุณจะท่องกราฟทีละระดับด้วยการค้นหาตามแนวกว้างและคิว deque

  • ระดับกลาง
  • อ่าน 2 นาที
  • ตัวอย่างที่รันได้ 1 ตัวอย่าง

บทนำ

ปัญหาที่ต้องแก้

ต้องใช้กี่ขั้นในการไปจากคนหนึ่งถึงอีกคนในเครือข่ายสังคม หรือจากช่องหนึ่งของเขาวงกตไปยังทางออก breadth-first search สำรวจเป็นวงตามระยะทาง ครั้งแรกที่มันไปถึง node หนึ่งจึงเป็นตามเส้นทางที่สั้นที่สุด

ลองนึกภาพแบบนี้

breadth-first search เหมือนระลอกคลื่นบนสระน้ำ โยนก้อนหินลงที่จุดเริ่ม และระลอกคลื่นไปถึงทุกอย่างที่ห่างหนึ่งขั้นก่อน แล้วทุกอย่างที่ห่างสองขั้น ไปเรื่อยๆ ไม่มีอะไรที่ไกลกว่าถูกแตะก่อนที่ทุกอย่างที่ใกล้กว่าจะถูกไปถึง

จากระลอกคลื่นบนสระสู่โค้ด
queue = deque(["A"])🪨 โยนก้อนหินลงที่ A
node = queue.popleft()🌊 หยิบ node ถัดไปตามลำดับระยะทาง
if neighbor not in visited:🔎 ยังไม่ได้ไปถึงใช่ไหม?
queue.append(neighbor)➕ เพิ่มเข้าวงถัดไป
node ที่ใกล้ที่สุดก่อน โดยใช้คิว
สรุปในประโยคเดียว

breadth-first search (BFS) ไปที่ทุก node ของกราฟทีละระดับจาก node เริ่มต้นโดยใช้คิว จึงหาเส้นทางที่สั้นที่สุดในกราฟที่ไม่มีน้ำหนักได้

ประเด็นสำคัญ

  1. queue เก็บ node ที่รอการสำรวจ โดยตัวที่เก่าที่สุดมาก่อน
  2. visited บันทึก node ที่เจอแล้ว ไม่มีตัวไหนถูกเพิ่มสองครั้ง และวงจรจึงวนไม่รู้จบไม่ได้
  3. node = queue.popleft() หยิบ node ถัดไป และเพื่อนบ้านที่ยังไม่ได้ไปของมันต่อท้ายคิว
  4. order แสดง A แล้วเพื่อนบ้านของมันคือ B และ C แล้ว D และ E ที่ไกลออกไปอีกหนึ่งระดับ

ใช้เมื่อไร?

  • เส้นทางที่สั้นที่สุดในกราฟที่ไม่มีน้ำหนัก ตาราง และเขาวงกต
  • ระดับความห่างในเครือข่ายสังคม
  • web crawler และการหาทุกอย่างที่ไปถึงได้จากจุดเริ่มต้น

เมื่อไรยังไม่จำเป็น

  • เส้นเชื่อมมีต้นทุนต่างกัน เช่น ระยะทางถนน: ใช้อัลกอริทึมของ Dijkstra
  • คุณต้องสำรวจเส้นทางหนึ่งให้สุดก่อนเส้นอื่น เช่น สำหรับ backtracking: ใช้ depth-first search

ภาพจำลอง การค้นหาตามแนวกว้าง (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)
สร้างปุ่ม Run สำหรับตัวอย่างนี้

ผลลัพธ์จากการรัน

['A', 'B', 'C', 'D', 'E']

อธิบายโค้ด

คิว queue เก็บโหนดที่รอการเยี่ยม และส่งออกตามลำดับที่เข้ามา เซต visited จำโหนดที่เจอแล้ว เพื่อไม่ให้เยี่ยมโหนดเดิมซ้ำเมื่อกราฟมีวงรอบ ลำดับการเยี่ยมคือ A, B, C, D, E และความซับซ้อนคือ O(V + E) โดย V คือจำนวนโหนดและ E คือจำนวนเส้นเชื่อม

เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python

แบบฝึกหัดเพิ่มเติม

ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก

  1. ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
  2. แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
  3. จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
รันในคอมไพเลอร์ Python →

ข้อผิดพลาดที่พบบ่อย

ทำเครื่องหมายว่าไปแล้วช้าเกินไป

ถ้า 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)

เรียนบทนี้จบแล้วใช่ไหม

ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า

ถัดไป: การค้นหาตามแนวลึก (DFS) ใน Python →

ฝึกด้วยโจทย์

ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI

โจทย์ทั้งหมด