อัลกอริทึมการค้นหาแบบกว้าง (BFS) พร้อมตัวอย่าง

อัลกอริทึม BFS (การค้นหาแบบกว้างก่อน) คืออะไร

การค้นหาตามความกว้าง (BFS) คืออัลกอริทึมที่ใช้สร้างกราฟข้อมูลหรือค้นหาโครงสร้างแบบต้นไม้หรือแบบสำรวจ BFS ย่อมาจากคำว่า Breadth-first search

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

เมื่ออัลกอริทึมเยี่ยมชมและทำเครื่องหมายโหนดเริ่มต้นแล้ว อัลกอริทึมจะเคลื่อนไปยังโหนดที่ยังไม่ได้เยี่ยมชมที่ใกล้ที่สุดและวิเคราะห์โหนดเหล่านั้น เมื่อเยี่ยมชมแล้ว โหนดทั้งหมดจะถูกทำเครื่องหมาย การวนซ้ำเหล่านี้จะดำเนินต่อไปจนกว่าจะเยี่ยมชมและทำเครื่องหมายโหนดทั้งหมดในกราฟสำเร็จ

การสำรวจเส้นทางกราฟคืออะไร

การข้ามกราฟเป็นวิธีที่ใช้กันทั่วไปในการค้นหาตำแหน่งจุดยอดในกราฟ เป็นอัลกอริธึมการค้นหาขั้นสูงที่สามารถวิเคราะห์กราฟด้วยความเร็วและความแม่นยำ พร้อมทั้งทำเครื่องหมายลำดับของจุดยอดที่เยี่ยมชม กระบวนการนี้ช่วยให้คุณสามารถเยี่ยมชมแต่ละโหนดในกราฟได้อย่างรวดเร็วโดยไม่ถูกล็อกในวงวนไม่สิ้นสุด

สถาปัตยกรรมของอัลกอริทึม BFS

1. ในระดับต่างๆ ของข้อมูล คุณสามารถทำเครื่องหมายโหนดใดๆ ว่าเป็นโหนดเริ่มต้นหรือโหนดเริ่มต้นเพื่อเริ่มการสำรวจ BFS จะเยี่ยมชมโหนดและทำเครื่องหมายว่าเยี่ยมชมแล้วและวางไว้ในคิว
2. ตอนนี้ BFS จะเยี่ยมชมโหนดที่ใกล้ที่สุดและยังไม่ได้เยี่ยมชมและทำเครื่องหมายไว้ ค่าเหล่านี้จะถูกเพิ่มลงในคิวด้วย คิวทำงานบน รุ่น FIFO.
3. ในลักษณะเดียวกัน โหนดที่เหลือที่ใกล้ที่สุดและยังไม่ได้เยี่ยมชมบนกราฟจะถูกวิเคราะห์ ทำเครื่องหมาย และเพิ่มลงในคิว รายการเหล่านี้จะถูกลบออกจากคิวเมื่อได้รับ และพิมพ์ออกมาเป็นผลลัพธ์

ทำไมเราต้องมีอัลกอริทึม BFS?

มีเหตุผลมากมายในการใช้ BFS Algorithm ในการค้นหาชุดข้อมูลของคุณ ปัจจัยที่สำคัญที่สุดบางประการที่ทำให้อัลกอรึทึมนี้เป็นตัวเลือกแรกของคุณ ได้แก่:

• BFS มีประโยชน์สำหรับการวิเคราะห์โหนดในกราฟและสร้างเส้นทางที่สั้นที่สุดในการเคลื่อนที่ผ่านสิ่งเหล่านี้
• BFS สามารถสำรวจกราฟโดยใช้จำนวนการวนซ้ำน้อยที่สุด
• สถาปัตยกรรมของอัลกอริทึม BFS นั้นเรียบง่ายและแข็งแกร่ง
• ผลลัพธ์ของอัลกอริทึม BFS นั้นมีความแม่นยำในระดับสูงเมื่อเทียบกับอัลกอริทึมอื่นๆ
• การวนซ้ำของ BFS นั้นราบรื่น และไม่มีความเป็นไปได้ที่อัลกอริธึมนี้จะติดปัญหาลูปไม่สิ้นสุด

อัลกอริทึมของบีเอฟเอสทำงานอย่างไร

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

อัลกอริทึม BFS จะเริ่มการทำงานจากโหนดแรกหรือโหนดเริ่มต้นในกราฟและดำเนินการอย่างละเอียด เมื่อดำเนินการผ่านโหนดเริ่มต้นสำเร็จแล้ว ก็จะเยี่ยมชมและทำเครื่องหมายจุดยอดที่ไม่ถูกดำเนินการถัดไปในกราฟ

ดังนั้น คุณสามารถพูดได้ว่าโหนดทั้งหมดที่อยู่ติดกับจุดยอดปัจจุบันได้รับการเยี่ยมชมและผ่านในรอบแรก ระเบียบวิธีคิวแบบง่าย ๆ จะถูกใช้เพื่อนำการทำงานของอัลกอริทึม BFS ไปใช้ และประกอบด้วยขั้นตอนต่อไปนี้:

ขั้นตอน 1)

แต่ละจุดยอดหรือโหนดในกราฟเป็นที่รู้จัก ตัวอย่างเช่น คุณสามารถทำเครื่องหมายโหนดเป็น V ได้

ขั้นตอน 2)

ในกรณีที่ไม่ได้เข้าถึงจุดยอด V ให้เพิ่มจุดยอด V ลงในคิว BFS

ขั้นตอน 3)

เริ่มการค้นหา BFS และหลังจากเสร็จสิ้น ทำเครื่องหมายจุดยอด V ว่าเยี่ยมชมแล้ว

ขั้นตอน 4)

คิว BFS ยังไม่ว่างเปล่า ดังนั้นจึงลบจุดยอด V ของกราฟออกจากคิว

ขั้นตอน 5)

ดึงจุดยอดที่เหลือทั้งหมดบนกราฟที่อยู่ติดกับจุดยอด V

ขั้นตอน 6)

สำหรับจุดยอดที่อยู่ติดกันแต่ละจุด สมมติว่า V1 ในกรณีที่ยังไม่ได้เยี่ยมชม ให้เพิ่ม V1 ลงในคิว BFS

ขั้นตอน 7)

BFS จะเยี่ยมชม V1 และทำเครื่องหมายว่าเยี่ยมชมแล้ว และลบออกจากคิว

ตัวอย่างอัลกอริทึม BFS

ขั้นตอน 1)

คุณมีกราฟของตัวเลขเจ็ดตัวตั้งแต่ 0 – 6

ขั้นตอน 2)

0 หรือศูนย์ถูกทำเครื่องหมายเป็นโหนดรูท

ขั้นตอน 3)

0 ถูกเยี่ยมชม ทำเครื่องหมาย และแทรกลงในโครงสร้างข้อมูลคิว

ขั้นตอน 4)

โหนดที่อยู่ติดกันและที่ไม่ได้เยี่ยมชมที่เหลืออยู่ 0 รายการจะถูกเยี่ยมชม ทำเครื่องหมาย และแทรกลงในคิว

ขั้นตอน 5)

การวนซ้ำตามเส้นทางจะถูกทำซ้ำจนกว่าจะมีการเยี่ยมชมโหนดทั้งหมด

กฎของอัลกอริทึม BFS

ต่อไปนี้เป็นกฎสำคัญสำหรับการใช้อัลกอริทึม BFS:

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

การประยุกต์ใช้อัลกอริทึม BFS

มาดูแอปพลิเคชันในชีวิตจริงบางส่วนที่การใช้อัลกอริทึม BFS มีประสิทธิภาพสูง

• กราฟที่ไม่ถ่วงน้ำหนัก: อัลกอริธึม BFS สามารถสร้างเส้นทางที่สั้นที่สุดและแผนผังการขยายขั้นต่ำได้อย่างง่ายดายเพื่อเยี่ยมชมจุดยอดทั้งหมดของกราฟในเวลาที่สั้นที่สุดเท่าที่จะเป็นไปได้ด้วยความแม่นยำสูง
• เครือข่าย P2P: BFS สามารถนำมาใช้เพื่อค้นหาโหนดที่อยู่ใกล้หรืออยู่ติดกันทั้งหมดในเครือข่ายเพียร์ทูเพียร์ ซึ่งจะทำให้ค้นหาข้อมูลที่ต้องการได้เร็วขึ้น
• โปรแกรมรวบรวมข้อมูลเว็บ: โปรแกรมค้นหาหรือโปรแกรมรวบรวมข้อมูลเว็บสามารถสร้างดัชนีหลายระดับได้อย่างง่ายดายโดยใช้ BFS การใช้งาน BFS เริ่มต้นจากแหล่งที่มา ซึ่งเป็นหน้าเว็บ จากนั้นจะเข้าชมลิงก์ทั้งหมดจากแหล่งที่มานั้น
• ระบบนำทาง: บีเอฟเอสสามารถช่วยค้นหาสถานที่ใกล้เคียงทั้งหมดจากที่ตั้งหลักหรือต้นทาง
• การแพร่ภาพผ่านเครือข่าย: แพ็กเก็ตที่ออกอากาศจะถูกแนะนำโดยอัลกอริธึม BFS เพื่อค้นหาและเข้าถึงโหนดทั้งหมดที่มีที่อยู่นั้น

สรุป

• การข้ามกราฟเป็นกระบวนการพิเศษที่ต้องใช้อัลกอริธึมในการเยี่ยมชม ตรวจสอบ และ/หรืออัปเดตทุกโหนดที่ไม่ได้เยี่ยมชมในโครงสร้างคล้ายต้นไม้ อัลกอริธึม BFS ทำงานบนหลักการที่คล้ายกัน
• อัลกอริธึมมีประโยชน์สำหรับการวิเคราะห์โหนดในกราฟและสร้างเส้นทางที่สั้นที่สุดในการเคลื่อนที่ผ่านสิ่งเหล่านี้
• อัลกอริธึมจะสำรวจกราฟด้วยจำนวนการวนซ้ำที่น้อยที่สุดและเวลาที่สั้นที่สุดเท่าที่จะเป็นไปได้
• BFS เลือกโหนดเดียว (จุดเริ่มต้นหรือจุดต้นทาง) ในกราฟ จากนั้นไปที่โหนดทั้งหมดที่อยู่ติดกับโหนดที่เลือก BFS เข้าถึงโหนดเหล่านี้ทีละรายการ
• ข้อมูลที่เยี่ยมชมและทำเครื่องหมายจะถูกจัดไว้ในคิวโดย BFS คิวทำงานแบบเข้าก่อนออกก่อน ดังนั้นองค์ประกอบที่อยู่ในกราฟก่อนจะถูกลบออกก่อนแล้วจึงพิมพ์ออกมา
• อัลกอริธึม BFS ไม่สามารถติดอยู่ในวงวนไม่สิ้นสุดได้
• เนื่องจากความแม่นยำสูงและการใช้งานที่มีประสิทธิภาพ BFS จึงถูกนำไปใช้ในโซลูชันในชีวิตจริงหลายอย่าง เช่น เครือข่าย P2P โปรแกรมรวบรวมข้อมูลเว็บ และการแพร่ภาพผ่านเครือข่าย