การค้นหากราฟในโครงสร้างข้อมูล

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

สำหรับการค้นหาในกราฟ มีสองวิธีที่แตกต่างกัน เทคนิคการค้นหาแบบกว้างก่อนและลึกก่อน

การค้นหาแบบกว้างก่อน (BFS)

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

Depth First Search (DFS)

Depth-First Search (DFS) เป็นอัลกอริธึมการข้ามผ่านกราฟ ในอัลกอริธึมนี้ จะมีการกำหนดจุดยอดเริ่มต้นหนึ่งจุด และเมื่อพบจุดยอดที่อยู่ติดกัน มันจะเคลื่อนไปยังจุดยอดที่อยู่ติดกันนั้นก่อนและพยายามสำรวจในลักษณะเดียวกัน มันเคลื่อนผ่านความลึกทั้งหมด เท่าที่มันจะไปได้ หลังจากนั้นมันจะย้อนย้อนไปถึงจุดยอดก่อนหน้าเพื่อค้นหาเส้นทางใหม่

ในการใช้ DFS ในลักษณะวนซ้ำ เราจำเป็นต้องใช้โครงสร้างข้อมูลสแต็ก หากเราต้องการทำแบบเรียกซ้ำ ไม่จำเป็นต้องใช้สแต็กภายนอก สามารถทำสแต็กภายในสำหรับการเรียกซ้ำได้