การค้นหาในกราฟ
กราฟเป็นโครงสร้างข้อมูลแบบ Non-linear เก็บข้อมูลในโหนด เชื่อมต่อด้วยเส้นขอบ (Edges) ต้องการค้นหาข้อมูลในกราฟมี 2 วิธีหลัก:
Breadth First Search (BFS)
BFS เป็นอัลกอริทึมการเดินทาง (Traversal) ไปเยี่ยมโหนดทั้งหมดของกราฟ เลือกโหนดหนึ่ง แล้วเยี่ยมโหนดติดกัน (Adjacent) ทีละตัว จบโหนดติดกันทั้งหมด จึงไปโหนดถัดไป ใช้ Queue ในการทำงาน: ใส่โหนดติดกันทั้งหมดเข้า Queue เมื่อจบ dequeue หนึ่งตัว แล้วเดินทางต่อจากโหนดนั้น
Depth First Search (DFS)
DFS เป็นอัลกอริทึม Traversal ให้โหนดเริ่มต้น เมื่อพบโหนดติดกัน จะเดินไปโหนดนั้นทันที แล้วเดินต่อไปในลักษณะเดียวกัน จะลึกลงไปในความลึก (Depth) มากที่สุดเท่าที่จะทำได้ แล้วค่อย Backtrack กลับมาหาเส้นทางใหม่
- แบบ Iterative: ใช้ Stack
- แบบ Recursive: ใช้ Call Stack ภายใน (ไม่ต้องการ Stack ภายนอก)
