การค้นหาตามแนวลึก (DFS) ใน Python
ในบทเรียนนี้ คุณจะท่องกราฟด้วยการค้นหาตามแนวลึกที่เขียนด้วยฟังก์ชันเรียกตัวเอง
บทนำ
ปัญหาที่ต้องแก้
การหาทางออกจากเขาวงกต การตรวจว่ากราฟมีวงจรไหม หรือการจัดลำดับงานที่ขึ้นต่อกัน ล้วนต้องตามเส้นทางหนึ่งไปให้สุดก่อนลองเส้นอื่น นั่นคือ depth-first search
ลองนึกภาพแบบนี้
depth-first search คือวิธีที่คุณสำรวจถ้ำด้วยม้วนเชือก คุณตามอุโมงค์หนึ่งลึกไปจนสุด เมื่อเจอทางตัน คุณตามเชือกกลับไปที่ทางแยกล่าสุดแล้วลองอุโมงค์ถัดไป คุณทำเครื่องหมายอุโมงค์ที่สำรวจแล้ว จึงไม่เดินซ้ำสองครั้ง
visited.add(node)🧵 ทำเครื่องหมายว่าอุโมงค์นี้สำรวจแล้วfor neighbor in graph[node]:🔀 ดูแต่ละอุโมงค์จากตรงนี้depth_first(neighbor, visited)⬇️ ลงลึกไปในอุโมงค์แรกที่ยังไม่สำรวจreturn order↩️ ทางตัน: ตามเชือกกลับdepth-first search (DFS) สำรวจกราฟโดยตามกิ่งหนึ่งให้ลึกที่สุดก่อนถอยกลับ มักใช้ recursion หรือสแต็ก
ประเด็นสำคัญ
visited.add(node)ทำเครื่องหมาย node วงจรจึงทำให้เกิด recursion ไม่รู้จบไม่ได้for neighbor in graph[node]:ดูเพื่อนบ้านทีละตัวorder.extend(depth_first(neighbor, visited))สำรวจทั้งกิ่งใต้เพื่อนบ้านหนึ่งตัวก่อนไปตัวถัดไป- ผลลัพธ์ไปที่ D ก่อน C เพราะกิ่งของ B ถูกทำจนเสร็จก่อน
ใช้เมื่อไร?
- หาเส้นทางใดก็ได้ แก้เขาวงกตและปริศนาด้วย backtracking
- ตรวจหาวงจรและจัดลำดับงานที่มีการขึ้นต่อกัน (topological sort)
- สำรวจทุกส่วนที่เชื่อมกันของกราฟ
เมื่อไรยังไม่จำเป็น
- คุณต้องการเส้นทางที่สั้นที่สุด: depth-first search อาจเจอเส้นทางยาวก่อน ให้ใช้ breadth-first search
- กราฟที่ลึกมาก: recursion อาจชนขีดจำกัดของ Python ให้ใช้สแต็กที่เขียนเอง
ภาพจำลอง การค้นหาตามแนวลึก (DFS) ใน Python
O(V + E)กด เล่น หรือ ทีละขั้น เพื่อดูการเปรียบเทียบและการย้ายข้อมูลแต่ละขั้น
โค้ดตัวอย่าง
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
def depth_first(node, visited=None):
visited = visited or set()
visited.add(node)
order = [node]
for neighbor in graph[node]:
if neighbor not in visited:
order.extend(depth_first(neighbor, visited))
return order
print(depth_first("A"))
ผลลัพธ์จากการรัน
['A', 'B', 'D', 'C', 'E']
อธิบายโค้ด
เซต visited จำโหนดที่เยี่ยมแล้ว เพื่อป้องกันการเยี่ยมซ้ำและลูปไม่รู้จบเมื่อกราฟมีวงรอบ การเรียกตัวเองแต่ละครั้งจะลงไปยังเพื่อนบ้านที่ยังไม่เยี่ยม โปรแกรมจึงเยี่ยม A, B, D ก่อน แล้วย้อนกลับไปเยี่ยม C และ E สแตกการเรียกทำหน้าที่เป็นสแตกของอัลกอริทึม และความซับซ้อนคือ O(V + E)
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัดเพิ่มเติม
ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก
- ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
- จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
ข้อผิดพลาดที่พบบ่อย
ใช้อาร์กิวเมนต์เริ่มต้นที่เปลี่ยนได้
visited=set() จะถูกใช้ร่วมกันระหว่างการเรียกที่แยกกัน
def depth_first(node, visited=set()):
def depth_first(node, visited=None):
visited = visited or set()
เรียนบทนี้จบแล้วใช่ไหม
ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า
ฝึกด้วยโจทย์
ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI
- Count Islands Count groups of connected land cells in a grid. ปานกลาง
- Strongly Connected Components นับกลุ่มของโหนดที่ทุกโหนดสามารถเข้าถึงกันและกันได้ทั้งหมด ยาก
- Longest Path in a DAG Find the heaviest path in a task dependency graph. ยาก