อัลกอริธึมการค้นหาแบบกว้างก่อน: ภาพรวม ความสำคัญ & การใช้งาน

กราฟอยู่รอบตัวเรา กราฟสามารถคิดได้ว่าเป็นเครือข่ายของโหนดและขอบที่เชื่อมต่อถึงกัน เพื่อนของคุณบน Facebook คนรู้จักของคุณบน LinkedIn หรือผู้ติดตาม Twitter/Instagram ถือเป็นกราฟโซเชียลของคุณ ในทำนองเดียวกัน หากคุณต้องการเดินทางจากจุด A ไปยังจุด B คุณสามารถทำได้ผ่านหลายเส้นทาง ซึ่งสามารถมองเห็นได้บน Google แผนที่

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

Graph Traversal คืออะไร?

Graph Traversal เป็นวิธีการเยี่ยมชมทุกโหนดในกราฟเพียงครั้งเดียวด้วยความเร็วและความแม่นยำ เป็นอัลกอริธึมการค้นหากราฟขั้นสูงที่ให้คุณพิมพ์ลำดับของโหนดที่เข้าชมโดยไม่ต้องวนซ้ำแบบอนันต์ มีอัลกอริธึมการข้ามผ่านกราฟมากมาย เช่น Depth-First Search , Breadth-First Search , อัลกอริธึมของ Djikstra , A-Star Algorithm และอื่นๆ

บทความนี้จะเจาะลึกลงไปใน อัลกอริธึมการค้นหาแบบกว้าง หรือ BFS

โครงสร้างกราฟ

ก่อนที่เราจะดูรายละเอียดภายใต้ฮูด BFS ให้เราทำความคุ้นเคยกับคำศัพท์ของกราฟด้วยความช่วยเหลือของกราฟด้านบน:

Root Node – โหนดที่คุณเริ่มกระบวนการข้ามผ่าน เพื่อความง่าย เราสามารถพิจารณาว่า A เป็นโหนดรูท

ระดับ – ระดับคือชุดของโหนดทั้งหมดที่อยู่ห่างจากโหนดรูทเท่ากัน ดังนั้นหากเราพิจารณาว่าโหนด A อยู่ที่ระดับ 0 โหนด B และ C อยู่ที่ระดับ 1 ในขณะที่โหนด D, E และ F อยู่ที่ระดับ 2 ฮิวริสติกอย่างง่ายสำหรับการกำหนดหมายเลขระดับของโหนดคือการนับจำนวน ของขอบระหว่างโหนดดังกล่าวและโหนดรูท โปรดทราบว่าวิธีนี้ใช้ได้เฉพาะเมื่อคุณกำหนดโหนดรูทให้อยู่ที่ระดับ 0

โหนด หลัก – โหนดหลักของโหนดคือโหนดที่อยู่เหนือระดับหนึ่งและอยู่ติดกับโหนดนั้น สามารถคิดได้ว่าเป็นโหนดที่โหนดดังกล่าวมีต้นกำเนิด A คือโหนดหลักของ B และ C

โหนดย่อย / โหนด ย่อย – โหนดที่แยกย่อยและอยู่ติดกับโหนดหลัก B และ C เป็นโหนดย่อยของ A

อ่าน: เทคนิคการสร้างภาพข้อมูล 10 อันดับแรก

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

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

ให้เราดูการดำเนินการคิวโดยละเอียดสำหรับอัลกอริทึม BFS สำหรับกราฟที่ระบุด้านบน:

() – หมายถึง คิว

[] – หมายถึงเอาต์พุตที่พิมพ์ออกมา

1. แทรก A ลงในคิว (a)
2. พิมพ์ A ใส่ B และ C ลงในคิว (cb)[a]
3. พิมพ์ B ใส่โหนดย่อย D และ E ลงในคิว (edc)[ba]
4. พิมพ์ C ใส่โหนดย่อย F ลงในคิว (fed)[cba]
5. พิมพ์ D ใส่โหนดย่อยลงในคิว ไม่มีเลย (เฟ)[dcba]
6. พิมพ์ E ซึ่งได้แทรกโหนดย่อย F ลงในคิวแล้ว (ฉ)[edcba]
7. พิมพ์ F. [fedcba]

อะไรทำให้อัลกอริทึม BFS มีความสำคัญ

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

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

ชำระเงิน: โครงการการแสดงข้อมูลที่คุณสามารถทำซ้ำได้

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

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

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

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

การนำทางด้วย GPS - BFS ใช้ประโยชน์จากระบบ GPS เพื่อแสดงตำแหน่งใกล้เคียงที่เป็นไปได้ทั้งหมดจากจุดเริ่มต้นของคุณ ช่วยให้คุณนำทางจากจุด A ไปยัง B ได้อย่างราบรื่น

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

เครือข่าย P2P – ทอร์เรนต์หรือเครือข่ายการแชร์ไฟล์อื่นๆ อาศัยการสื่อสารแบบ P2P BFS ทำงานได้ดีมากในการค้นหาโหนดที่ใกล้ที่สุด เพื่อให้การถ่ายโอนข้อมูลทำได้เร็วขึ้น

อ่านเพิ่มเติม: ประโยชน์ของการสร้างภาพข้อมูล

บทสรุป

Ergo อัลกอริธึมการค้นหาแบบกว้างก่อน เป็นหนึ่งในอัลกอริธึมที่สำคัญที่สุดของอินเทอร์เน็ตสมัยใหม่ หวังว่าบล็อกนี้จะเป็นจุดเริ่มต้นที่สะดวกในการสำรวจอัลกอริทึมการค้นหาของคุณ

เราขอแนะนำให้คุณเลือก PG Diploma in Data Science ที่นำเสนอโดย IIIT Bangalore ซึ่งโฮสต์บน upGrad เพราะที่นี่คุณสามารถรับคำถาม 1-1 กับผู้สอนหลักสูตรได้ ไม่เพียงแค่เน้นการเรียนรู้เชิงทฤษฎีเท่านั้น แต่ยังให้ความสำคัญกับความรู้เชิงปฏิบัติ ซึ่งเป็นสิ่งสำคัญในการเตรียมความพร้อมให้ผู้เรียนพร้อมสำหรับการเผชิญหน้าโครงการในโลกแห่งความเป็นจริง และมอบใบรับรอง NASSCOM ฉบับที่ 1 ของอินเดียแก่คุณ ซึ่งช่วยให้คุณได้งานที่ได้ค่าตอบแทนสูงใน Data Science