BFS และ DFS เป็นอัลกอริธึมการข้ามผ่านกราฟ
BFS
อัลกอริธึมการค้นหาแบบกว้าง (BFS) จะข้ามกราฟในลักษณะที่กว้างและใช้คิวเพื่อจดจำจุดยอดถัดไปเพื่อเริ่มการค้นหาเมื่อจุดสิ้นสุดเกิดขึ้นในการวนซ้ำใดๆ
DFS
อัลกอริธึม Depth First Search (DFS) เคลื่อนที่ผ่านกราฟในลักษณะเชิงลึกและใช้สแต็กเพื่อจดจำจุดยอดถัดไปเพื่อเริ่มการค้นหาเมื่อจุดบอดเกิดขึ้นในทุก ๆ ครั้ง
ต่อไปนี้เป็นข้อแตกต่างที่สำคัญระหว่าง BFS และ DFS
| ซีเนียร์ เลขที่ | คีย์ | BFS | DFS |
|---|---|---|---|
| 1 | คำจำกัดความ | BFS ย่อมาจาก Breadth First Search | DFS ย่อมาจาก Depth First Search |
| 2 | โครงสร้างข้อมูล | BFS ใช้ Queue เพื่อค้นหาเส้นทางที่สั้นที่สุด | DFS ใช้ Stack เพื่อค้นหาเส้นทางที่สั้นที่สุด |
| 3 | ที่มา | BFS จะดีกว่าเมื่อเป้าหมายอยู่ใกล้แหล่งที่มามากขึ้น | DFS จะดีกว่าเมื่อเป้าหมายอยู่ไกลจากแหล่งที่มา |
| 4 | เหมาะสำหรับโครงสร้างการตัดสินใจ | เนื่องจาก BFS พิจารณาเพื่อนบ้านทั้งหมด จึงไม่เหมาะกับแผนผังการตัดสินใจที่ใช้ในเกมพัซเซิล | DFS เหมาะสมกว่าสำหรับโครงสร้างการตัดสินใจ เช่นเดียวกับการตัดสินใจครั้งเดียว เราต้องสำรวจเพิ่มเติมเพื่อเพิ่มการตัดสินใจ ถ้าเราได้ข้อสรุป เราก็ชนะ |
| 5 | ความเร็ว | BFS ช้ากว่า DFS | DFS เร็วกว่า BFS |
| 6 | ความซับซ้อนของเวลา | ความซับซ้อนของเวลาของ BFS =O(V+E) โดยที่ V คือจุดยอดและ E คือขอบ | ความซับซ้อนของเวลาของ DFS ก็คือ O(V+E) โดยที่ V คือจุดยอดและ E คือขอบ |
