อัลกอริทึมการค้นหาแบบกว้าง (BFS) พร้อมตัวอย่าง
ซาราห์ เฉิน
⚡ สรุปอย่างชาญฉลาด
การค้นหาแบบกว้าง (Breadth First Search หรือ BFS) เป็นอัลกอริทึมที่สำรวจกราฟทีละระดับ โดยเยี่ยมชมเพื่อนบ้านทั้งหมดของโหนดก่อนที่จะลงลึกไปในระดับถัดไป อัลกอริทึมนี้ใช้คิวแบบ FIFO และค้นหาเส้นทางที่สั้นที่สุดในกราฟที่ไม่มีน้ำหนักโดยไม่เกิดวงวนอนันต์
อัลกอริทึม BFS (การค้นหาแบบกว้างก่อน) คืออะไร
การค้นหาแบบกว้าง (Breadth-first search หรือ BFS) เป็นอัลกอริทึมที่ใช้ในการสร้างกราฟข้อมูล หรือค้นหาในโครงสร้างแบบต้นไม้ หรือการสำรวจโครงสร้างต่างๆ ชื่อเต็มของ BFS คือ Breadth-first search
อัลกอริทึมจะเข้าเยี่ยมชมและทำเครื่องหมายโหนดสำคัญทั้งหมดในกราฟอย่างมีประสิทธิภาพด้วยรูปแบบความกว้างที่แม่นยำ อัลกอริทึมนี้จะเลือกโหนดเดียว (จุดเริ่มต้นหรือจุดต้นทาง) ในกราฟ จากนั้นจึงเข้าเยี่ยมชมโหนดทั้งหมดที่อยู่ติดกับโหนดที่เลือก โปรดจำไว้ว่า BFS จะเข้าถึงโหนดเหล่านี้ทีละโหนด
เมื่ออัลกอริทึมเยี่ยมชมและทำเครื่องหมายโหนดเริ่มต้นแล้ว อัลกอริทึมจะเคลื่อนไปยังโหนดที่ยังไม่ได้เยี่ยมชมที่ใกล้ที่สุดและวิเคราะห์โหนดเหล่านั้น เมื่อเยี่ยมชมแล้ว โหนดทั้งหมดจะถูกทำเครื่องหมาย การวนซ้ำเหล่านี้จะดำเนินต่อไปจนกว่าจะเยี่ยมชมและทำเครื่องหมายโหนดทั้งหมดในกราฟสำเร็จ
การสำรวจเส้นทางกราฟคืออะไร
การข้ามกราฟเป็นวิธีที่ใช้กันทั่วไปในการค้นหาตำแหน่งจุดยอดในกราฟ เป็นอัลกอริธึมการค้นหาขั้นสูงที่สามารถวิเคราะห์กราฟด้วยความเร็วและความแม่นยำ พร้อมทั้งทำเครื่องหมายลำดับของจุดยอดที่เยี่ยมชม กระบวนการนี้ช่วยให้คุณสามารถเยี่ยมชมแต่ละโหนดในกราฟได้อย่างรวดเร็วโดยไม่ถูกล็อกในวงวนไม่สิ้นสุด
สถาปัตยกรรมของอัลกอริทึม BFS
- ในระดับต่างๆ ของข้อมูล คุณสามารถกำหนดโหนดใดก็ได้เป็นโหนดเริ่มต้นหรือโหนดแรกเพื่อเริ่มการสำรวจ อัลกอริทึม BFS จะเยี่ยมชมโหนดนั้น ทำเครื่องหมายว่าเยี่ยมชมแล้ว และเพิ่มลงในคิว
- ตอนนี้ BFS จะเข้าเยี่ยมชมโหนดที่อยู่ใกล้ที่สุดและยังไม่เคยเยี่ยมชมมาก่อน แล้วทำเครื่องหมายไว้ ค่าเหล่านี้จะถูกเพิ่มเข้าไปในคิวด้วย คิวทำงานบน รุ่น FIFO.
- ในทำนองเดียวกัน โหนดที่อยู่ใกล้ที่สุดและยังไม่เคยถูกเยี่ยมชมบนกราฟจะถูกวิเคราะห์ ทำเครื่องหมาย และเพิ่มลงในคิว รายการเหล่านี้จะถูกลบออกจากคิวเมื่อได้รับ และพิมพ์ออกมาเป็นผลลัพธ์
ทำไมเราต้องมีอัลกอริทึม BFS?
มีเหตุผลมากมายที่ควรใช้อัลกอริธึม BFS ในการค้นหาชุดข้อมูลของคุณ เหตุผลสำคัญบางประการที่ทำให้อัลกอริธึมนี้เป็นตัวเลือกแรกของคุณ ได้แก่:
- 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 – First in First Out) โครงสร้างข้อมูล ถูกนำมาใช้โดยบีเอฟเอส
- คุณกำหนดโหนดใดก็ได้ในกราฟเป็นโหนดราก แล้วเริ่มสำรวจข้อมูลจากโหนดนั้น
- BFS จะสำรวจโหนดทั้งหมดในกราฟและทำการดรอปping เมื่อเสร็จสมบูรณ์แล้ว
- BFS เยี่ยมชมโหนดที่อยู่ติดกันซึ่งไม่ได้เยี่ยมชม ทำเครื่องหมายว่าเสร็จสิ้น และแทรกลงในคิว
- หากไม่พบจุดยอดที่อยู่ติดกัน ระบบจะลบจุดยอดก่อนหน้าออกจากคิว
- อัลกอริทึม BFS จะวนซ้ำไปเรื่อยๆ จนกว่าจุดยอดทั้งหมดในกราฟจะถูกสำรวจสำเร็จและทำเครื่องหมายว่าเสร็จสมบูรณ์แล้ว
- ไม่มีการวนซ้ำที่เกิดจาก BFS ระหว่างการข้ามข้อมูลจากโหนดใดๆ
การประยุกต์ใช้อัลกอริทึม BFS
มาดูแอปพลิเคชันในชีวิตจริงบางส่วนที่การใช้อัลกอริทึม BFS มีประสิทธิภาพสูง
- กราฟที่ไม่ถ่วงน้ำหนัก: อัลกอริทึม BFS สามารถสร้างเส้นทางที่สั้นที่สุดและต้นไม้แผ่คลุมขั้นต่ำเพื่อเยี่ยมชมจุดยอดทั้งหมดของกราฟได้ในเวลาที่สั้นที่สุดด้วยความแม่นยำสูง
- เครือข่าย P2P: BFS สามารถนำมาใช้เพื่อค้นหาโหนดที่อยู่ใกล้ที่สุดหรือโหนดข้างเคียงทั้งหมดในเครือข่ายแบบ Peer-to-Peer ซึ่งจะช่วยให้ค้นหาข้อมูลที่ต้องการได้เร็วขึ้น
- โปรแกรมรวบรวมข้อมูลเว็บ: โปรแกรมค้นหาหรือโปรแกรมรวบรวมข้อมูลเว็บสามารถสร้างดัชนีหลายระดับได้อย่างง่ายดายโดยใช้ BFS การใช้งาน BFS เริ่มต้นจากแหล่งที่มา ซึ่งเป็นหน้าเว็บ จากนั้นจะเข้าชมลิงก์ทั้งหมดจากแหล่งที่มานั้น
- ระบบนำทาง: บีเอฟเอสสามารถช่วยค้นหาสถานที่ใกล้เคียงทั้งหมดจากที่ตั้งหลักหรือต้นทาง
- การแพร่ภาพผ่านเครือข่าย: แพ็กเก็ตที่ออกอากาศจะถูกแนะนำโดยอัลกอริธึม BFS เพื่อค้นหาและเข้าถึงโหนดทั้งหมดที่มีที่อยู่นั้น
