DFS — อธิบายอัลกอริทึมการค้นหาเชิงลึก (Depth-First Search)

Depth-first search หรือ DFS คืออัลกอริทึมสำหรับสำรวจต้นไม้หรือกราฟ โดยจะตามเส้นทางหนึ่งไปให้ลึกที่สุดก่อน แล้วค่อยย้อนกลับ พูดง่าย ๆ คือ DFS จะลงลึกไปเรื่อย ๆ จนไปต่อไม่ได้ แล้วจึงกลับไปยังจุดล่าสุดที่ยังมีแขนงอื่นให้สำรวจ

ถ้าจะจำแค่แนวคิดเดียว ให้จำสิ่งนี้ไว้: DFS คือ “ลงลึกก่อน แล้วค่อยย้อนกลับ”

Depth-First Search ทำอะไร

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

การย้อนกลับนี่เองคือพฤติกรรมสำคัญของ DFS ในการเขียนแบบเวียนเกิด (recursive) call stack จะจัดการเรื่องนี้ให้อัตโนมัติ ส่วนในการเขียนแบบวนซ้ำ (iterative) จะใช้ stack อย่างชัดเจนเพื่อทำหน้าที่เดียวกัน

ทำไมลำดับของ DFS ถึงเปลี่ยนได้

DFS ไม่มีลำดับการเยี่ยมชมที่ตายตัวเพียงแบบเดียว ลำดับที่ได้ขึ้นอยู่กับว่าเราพิจารณาเพื่อนบ้านตามลำดับใด

ตัวอย่างเช่น ถ้าโหนดหนึ่งมีเพื่อนบ้านเป็น $B$ และ $C$ การไปที่ $B$ ก่อนอาจให้ลำดับ DFS ต่างจากการไปที่ $C$ ก่อน แต่ทั้งสองกรณีก็ยังเป็น DFS เหมือนกัน เพราะกฎยังเหมือนเดิมคือ ต้องลงลึกก่อนค่อยไปสำรวจแขนงข้างเคียง

ตัวอย่าง DFS บนกราฟขนาดเล็ก

สมมติว่ากราฟมีการเชื่อมต่อดังนี้:

• $A$ เชื่อมกับ $B$ และ $C$
• $B$ เชื่อมกับ $D$ และ $E$
• $C$ เชื่อมกับ $F$

สมมติว่าเราตรวจดูเพื่อนบ้านจากซ้ายไปขวาเสมอ และเริ่มที่ $A$

DFS จะดำเนินไปดังนี้:

1. เยี่ยมชม $A$
2. ไปที่ $B$
3. ไปที่ $D$
4. $D$ ไม่มีเพื่อนบ้านที่ยังไม่เคยเยี่ยมชม จึงย้อนกลับไปที่ $B$
5. จาก $B$ ไปที่ $E$
6. $E$ เสร็จแล้ว จึงย้อนกลับไปที่ $B$ แล้วกลับไปที่ $A$
7. จาก $A$ ไปที่ $C$
8. จาก $C$ ไปที่ $F$

ดังนั้น ลำดับการเยี่ยมชมแบบ DFS ที่ถูกต้องแบบหนึ่งคือ:

$$A, B, D, E, C, F$$

แนวคิดสำคัญคือ DFS จะสำรวจฝั่ง $A \to B$ ให้เสร็จก่อน แล้วจึงเริ่มฝั่ง $A \to C$ ถ้าคุณเปลี่ยนลำดับของเพื่อนบ้าน ลำดับการเยี่ยมชมก็อาจเปลี่ยนตามไปด้วย

ทำไมการย้อนกลับจึงใช้ Stack

DFS ต้องมีวิธีจำเสมอว่าจะต้องกลับไปที่ไหนหลังจากเจอทางตัน นี่จึงเป็นเหตุผลที่ stack ปรากฏขึ้นอย่างเป็นธรรมชาติใน DFS

ใน DFS แบบเวียนเกิด แต่ละการเรียกฟังก์ชันจะรออยู่ขณะที่การค้นหาลงลึกต่อไป และโปรแกรมจะย้อนกลับตามลำดับย้อนกลับเมื่อเกิดการย้อนกลับ ใน DFS แบบวนซ้ำ คุณจะ push โหนดลงใน stack และ pop ออกเมื่อถึงเวลาต้องสำรวจต่อจากจุดล่าสุดที่ยังทำไม่เสร็จ

ความซับซ้อนเชิงเวลาและเชิงพื้นที่ของ DFS

ถ้ากราฟถูกเก็บในรูป adjacency list และแต่ละจุดยอดถูกทำเครื่องหมายตั้งแต่ครั้งแรกที่ถูกเยี่ยมชม DFS จะทำงานในเวลา

$$O(V + E)$$

สำหรับส่วนของกราฟที่เข้าถึงได้ โดยที่ $V$ คือจำนวนจุดยอด และ $E$ คือจำนวนเส้นเชื่อม

พื้นที่เพิ่มเติมที่ใช้มักเป็น

$$O(V)$$

เพราะโครงสร้างสำหรับเก็บสถานะ visited และ recursion stack หรือ explicit stack ต่างก็อาจโตตามจำนวนจุดยอดได้

ข้อผิดพลาดที่พบบ่อยใน DFS

ลืมทำเครื่องหมายโหนดที่เยี่ยมชมแล้ว

ในกราฟทั่วไป การลืมตรวจสอบ visited อาจทำให้ DFS วนอยู่ในวัฏจักรตลอดไป แม้แต่ในต้นไม้ที่เก็บเป็นกราฟไม่มีทิศทาง คุณก็ยังต้องหลีกเลี่ยงการเดินกลับไปยังโหนดพ่อทันที เว้นแต่โค้ดของคุณจะจัดการกรณีนั้นไว้อย่างชัดเจน

คิดว่า DFS หาเส้นทางที่สั้นที่สุดได้เสมอ

DFS หาเส้นทางได้ แต่โดยทั่วไปไม่ได้รับประกันว่าเป็นเส้นทางที่สั้นที่สุดในกราฟไม่มีน้ำหนัก ถ้าเป้าหมายคือหาเส้นทางที่สั้นที่สุด และทุกเส้นเชื่อมมีน้ำหนักเท่ากัน BFS มักเป็นจุดเริ่มต้นที่เหมาะกว่า

คิดว่าลำดับของ DFS มีได้แบบเดียว

ลำดับขึ้นอยู่กับลำดับของเพื่อนบ้าน ถ้าลำดับนั้นเปลี่ยน ลำดับการท่องกราฟก็อาจเปลี่ยนตามได้

Depth-First Search ใช้เมื่อไร

DFS มีประโยชน์เมื่อคุณต้องการสำรวจโครงสร้าง ไม่ใช่แค่หาระยะใกล้ที่สุดก่อน การใช้งานที่พบบ่อย ได้แก่:

• ตรวจสอบว่าโหนดหนึ่งเข้าถึงได้หรือไม่
• หา connected components
• ตรวจจับวัฏจักรในกราฟบางประเภท
• ท่องต้นไม้
• แก้ปัญหาแบบ backtracking เช่น เขาวงกตหรือการค้นหาในปริศนา

เหตุผลหลักที่ DFS ปรากฏบ่อยมากคือแนวคิด “ลงลึกก่อน แล้วค่อยย้อนกลับ” สอดคล้องกับโครงสร้างของปัญหาแบบเวียนเกิดจำนวนมาก

DFS เทียบกับ BFS: ความต่างในทางปฏิบัติ

DFS จะลงไปตามแขนงหนึ่งก่อน ส่วน BFS จะสำรวจทุกโหนดที่อยู่ในระยะเดียวกันก่อน แล้วจึงค่อยไปยังระยะถัดไป

ถ้าคุณสนใจการสำรวจให้ครบหรือสนใจโครงสร้างแบบเวียนเกิด DFS มักเป็นทางเลือกที่เป็นธรรมชาติ แต่ถ้าคุณสนใจเส้นทางที่สั้นที่สุดในกราฟไม่มีน้ำหนัก BFS มักเป็นตัวเลือกแรกที่ปลอดภัยกว่า

ลองทำการท่องกราฟแบบคล้ายกัน

วาดกราฟเล็ก ๆ ที่มีหกโหนด แล้วกำหนดลำดับของเพื่อนบ้านให้แน่นอน ลองทำ DFS ด้วยมือและจดให้ชัดว่าคุณเดินหน้าเมื่อไรและย้อนกลับเมื่อไร ถ้าลำดับเปลี่ยนหลังจากคุณสลับลำดับเพื่อนบ้าน นั่นไม่ใช่บั๊ก แต่มันเป็นส่วนหนึ่งของวิธีทำงานของ DFS