The latest articles on DEV Community by MINNIE EIEI (@mintada). https://dev.to/mintada https://media2.dev.to/dynamic/image/width=90,height=90,fit=cover,gravity=auto,format=auto/https:%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Fuser%2Fprofile_image%2F3041700%2F605a68a6-6515-4d57-b7d6-90be47f7a12c.jpg https://dev.to/mintada en MINNIE EIEI Fri, 11 Apr 2025 14:01:24 +0000 https://dev.to/mintada/kaarkhnhaaaebb-breadth-first-search-bfs-aelakaarprayuktaichngaan-54d https://dev.to/mintada/kaarkhnhaaaebb-breadth-first-search-bfs-aelakaarprayuktaichngaan-54d <p>Breadth First Search (BFS) คือหนึ่งในอัลกอริธึมพื้นฐานในสาขาวิทยาการคอมพิวเตอร์ โดยเฉพาะในหัวข้อการค้นหาเส้นทาง กราฟ และโครงสร้างข้อมูลแบบต้นไม้ (Tree/Graph Traversal) BFS มีจุดเด่นในการสำรวจข้อมูลในลำดับชั้น (level-order traversal) ซึ่งเหมาะกับปัญหาที่ต้องการค้นหาเส้นทางที่สั้นที่สุด หรือสำรวจโหนดทั้งหมดในลำดับที่เป็นธรรมชาติ</p> <p>BFS จะเริ่มต้นจากโหนดต้นทาง แล้วทำการสำรวจโหนดที่อยู่ใกล้ที่สุดก่อน (ตามลำดับระดับ) จากนั้นจึงค่อย ๆ ขยายการสำรวจออกไปยังโหนดที่อยู่ห่างขึ้นในลำดับถัดไป โดยจะใช้ Queue (คิว) เป็นโครงสร้างข้อมูลหลักในการจัดการลำดับการเข้าถึงโหนด</p> <p><strong>ข้อดีของการค้นหาแบบ BFS</strong></p> <ol> <li><p>หาเส้นทางที่สั้นที่สุดในกราฟที่มีน้ำหนักเท่ากันได้</p></li> <li><p>ใช้งานง่ายและเข้าใจง่าย เหมาะสำหรับผู้เริ่มต้น</p></li> <li><p>เหมาะกับปัญหาประเภทการค้นหากว้าง เช่น เขาวงกต, เกม, แผนที่</p></li> </ol> <p><strong>ตัวอย่างโค้ด BFS ด้วย Python</strong></p> <p><a href="https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2F2pn0ovjne1tlgw1blprs.png" class="article-body-image-wrapper"><img src="https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2F2pn0ovjne1tlgw1blprs.png" alt="Image description" width="580" height="534"></a></p> <p>ผลลัพธ์ที่ได้จาก BFS คือ: A B C D E F ซึ่งแสดงให้เห็นว่า BFS เยี่ยมชมโหนดตามระดับความใกล้</p> <p><strong>การใช้งานจริงของ BFS</strong></p> <p><a href="https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fwwca81pvkjc0wlg9sgyq.png" class="article-body-image-wrapper"><img src="https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fwwca81pvkjc0wlg9sgyq.png" alt="Image description" width="765" height="675"></a></p> <p>โค้ดตัวอย่างนี้แสดงการนำ BFS ไปประยุกต์ใช้ในการค้นหาเส้นทางที่สั้นที่สุดในเขาวงกต โดยผลลัพธ์จะเป็นลิสต์ของพิกัดที่แสดงถึงเส้นทางจากจุดเริ่มต้นไปยังจุดสิ้นสุด</p> <p><strong>การเปรียบเทียบ BFS กับ DFS (Depth First Search)</strong></p> <p><a href="https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2F5jqbdxkfue9aci4bp3o6.png" class="article-body-image-wrapper"><img src="https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2F5jqbdxkfue9aci4bp3o6.png" alt="Image description" width="800" height="204"></a></p> <p><strong>สรุป</strong></p> <p>Breadth First Search เป็นหนึ่งในอัลกอริธึมการค้นหาที่มีความสำคัญอย่างยิ่งในวงการคอมพิวเตอร์และข้อมูล โดยเฉพาะการทำงานกับกราฟ โครงสร้างเครือข่าย และเกม อัลกอริธึมนี้แม้จะเรียบง่ายแต่มีประโยชน์มหาศาล และสามารถประยุกต์ใช้กับสถานการณ์จริงได้หลากหลาย</p> <p>การทำความเข้าใจ BFS อย่างลึกซึ้งจะช่วยให้สามารถพัฒนาอัลกอริธึมอื่น ๆ ที่ซับซ้อนยิ่งขึ้นได้ในอนาคต เช่น A*, Dijkstra หรือ Graph Search ที่ใช้ใน AI</p>