BFS (Breadth First Search) และ DFS (Depth First Search) เป็นอัลกอริทึมการเดินทางกราฟ (Graph Traversal Algorithms)
BFS
อัลกอริทึม Breadth First Search เดินทางกราฟแบบ กว้าง (Breadthward) ใช้ Queue (คิว) จดจำโหนดถัดไปเมื่อถึง Dead End
DFS
อัลกอริทึม Depth First Search เดินทางกราฟแบบ ลึก (Depthward) ใช้ Stack (สแต็ก) จดจำโหนดถัดไปเมื่อถึง Dead End
ตารางเปรียบเทียบ
| ลำดับ | หัวข้อ | BFS | DFS |
|---|---|---|---|
| 1 | ความหมาย | Breadth First Search | Depth First Search |
| 2 | โครงสร้างข้อมูล | Queue – หา Shortest Path | Stack – หา Shortest Path |
| 3 | เหมาะกับเป้าหมาย | Target ใกล้ Source | Target ไกลจาก Source |
| 4 | Decision Tree | ไม่เหมาะ (พิจารณาเพื่อนบ้านทั้งหมด) | เหมาะกว่า (ตัดสินใจหนึ่ง แล้วลึกเข้าไป) |
| 5 | ความเร็ว | ช้ากว่า DFS | เร็วกว่า BFS |
| 6 | Time Complexity | O(V+E) V=โหนด E=ขอบ | O(V+E) V=โหนด E=ขอบ |
