โครงสร้างข้อมูล - การข้ามผ่านครั้งแรกแบบกว้าง

อัลกอริทึมการค้นหาแรกกว้าง (BFS) จะข้ามกราฟในการเคลื่อนที่แบบกว้างและใช้คิวเพื่อจำเพื่อให้ได้จุดยอดถัดไปเพื่อเริ่มการค้นหาเมื่อมีทางตันเกิดขึ้นในการวนซ้ำใด ๆ

ดังตัวอย่างที่ให้ไว้ข้างต้นอัลกอริทึม BFS จะข้ามจาก A ไป B ไปยัง E ถึง F จากนั้นไปที่ C และ G สุดท้ายถึง D มันใช้กฎต่อไปนี้

  • Rule 1- เยี่ยมชมจุดยอดที่ไม่ได้เข้าชมที่อยู่ติดกัน ทำเครื่องหมายว่าเยี่ยมชมแล้ว แสดงมัน แทรกไว้ในคิว

  • Rule 2 - หากไม่พบจุดยอดที่อยู่ติดกันให้ลบจุดยอดแรกออกจากคิว

  • Rule 3 - ทำซ้ำกฎ 1 และกฎ 2 จนกว่าคิวจะว่างเปล่า

ขั้นตอน ข้ามผ่าน คำอธิบาย
1
เริ่มต้นคิว
2
เราเริ่มจากการเยี่ยมชม S (โหนดเริ่มต้น) และทำเครื่องหมายว่าเยี่ยมชมแล้ว
3
จากนั้นเราจะเห็นโหนดที่อยู่ติดกันที่ไม่ได้มาจาก S. ในตัวอย่างนี้เรามีสามโหนด แต่เราเลือกตามตัวอักษรAทำเครื่องหมายว่าเยี่ยมชมแล้วและจัดคิว
4
ถัดไปโหนดที่อยู่ติดกันที่ไม่ได้เข้าชมจาก S คือ B. เราทำเครื่องหมายว่าเยี่ยมชมและจัดคิว
5
ถัดไปโหนดที่อยู่ติดกันที่ไม่ได้เข้าชมจาก S คือ C. เราทำเครื่องหมายว่าเยี่ยมชมและจัดคิว
6
ตอนนี้ Sไม่เหลือโหนดที่อยู่ติดกัน ดังนั้นเราจึงตัดสินใจและค้นหาA.
7
จาก A เรามี Dเป็นโหนดที่อยู่ติดกันที่ไม่ได้เข้าชม เราทำเครื่องหมายว่าเยี่ยมชมและจัดคิว

ในขั้นตอนนี้เราจะไม่เหลือโหนดที่ไม่มีเครื่องหมาย (ไม่ได้เยี่ยมชม) แต่ตามอัลกอริทึมนั้นเรายังคงทำการจัดคิวเพื่อให้ได้โหนดที่ไม่ได้เข้าชมทั้งหมด เมื่อคิวว่างโปรแกรมจะสิ้นสุดลง

การดำเนินการตามขั้นตอนวิธีนี้ในการเขียนโปรแกรมภาษา C สามารถเห็นได้ที่นี่