อัลกอริทึม Python

การค้นหาตามแนวลึก (DFS) ใน Python

ในบทเรียนนี้ คุณจะท่องกราฟด้วยการค้นหาตามแนวลึกที่เขียนด้วยฟังก์ชันเรียกตัวเอง

  • ระดับกลาง
  • อ่าน 2 นาที
  • ตัวอย่างที่รันได้ 1 ตัวอย่าง

บทนำ

ปัญหาที่ต้องแก้

การหาทางออกจากเขาวงกต การตรวจว่ากราฟมีวงจรไหม หรือการจัดลำดับงานที่ขึ้นต่อกัน ล้วนต้องตามเส้นทางหนึ่งไปให้สุดก่อนลองเส้นอื่น นั่นคือ 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 หรือสแต็ก

ประเด็นสำคัญ

  1. visited.add(node) ทำเครื่องหมาย node วงจรจึงทำให้เกิด recursion ไม่รู้จบไม่ได้
  2. for neighbor in graph[node]: ดูเพื่อนบ้านทีละตัว
  3. order.extend(depth_first(neighbor, visited)) สำรวจทั้งกิ่งใต้เพื่อนบ้านหนึ่งตัวก่อนไปตัวถัดไป
  4. ผลลัพธ์ไปที่ D ก่อน C เพราะกิ่งของ B ถูกทำจนเสร็จก่อน

ใช้เมื่อไร?

  • หาเส้นทางใดก็ได้ แก้เขาวงกตและปริศนาด้วย backtracking
  • ตรวจหาวงจรและจัดลำดับงานที่มีการขึ้นต่อกัน (topological sort)
  • สำรวจทุกส่วนที่เชื่อมกันของกราฟ

เมื่อไรยังไม่จำเป็น

  • คุณต้องการเส้นทางที่สั้นที่สุด: depth-first search อาจเจอเส้นทางยาวก่อน ให้ใช้ breadth-first search
  • กราฟที่ลึกมาก: recursion อาจชนขีดจำกัดของ Python ให้ใช้สแต็กที่เขียนเอง

ภาพจำลอง การค้นหาตามแนวลึก (DFS) ใน Python

O(V + E)

กด เล่น หรือ ทีละขั้น เพื่อดูการเปรียบเทียบและการย้ายข้อมูลแต่ละขั้น

โค้ดตัวอย่าง

รันโค้ด →
main.py
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"))
สร้างปุ่ม Run สำหรับตัวอย่างนี้

ผลลัพธ์จากการรัน

['A', 'B', 'D', 'C', 'E']

อธิบายโค้ด

เซต visited จำโหนดที่เยี่ยมแล้ว เพื่อป้องกันการเยี่ยมซ้ำและลูปไม่รู้จบเมื่อกราฟมีวงรอบ การเรียกตัวเองแต่ละครั้งจะลงไปยังเพื่อนบ้านที่ยังไม่เยี่ยม โปรแกรมจึงเยี่ยม A, B, D ก่อน แล้วย้อนกลับไปเยี่ยม C และ E สแตกการเรียกทำหน้าที่เป็นสแตกของอัลกอริทึม และความซับซ้อนคือ O(V + E)

เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python

แบบฝึกหัดเพิ่มเติม

ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก

  1. ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
  2. แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
  3. จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
รันในคอมไพเลอร์ Python →

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

ใช้อาร์กิวเมนต์เริ่มต้นที่เปลี่ยนได้

visited=set() จะถูกใช้ร่วมกันระหว่างการเรียกที่แยกกัน

ปัญหา
def depth_first(node, visited=set()):
วิธีแก้
def depth_first(node, visited=None):
    visited = visited or set()

เรียนบทนี้จบแล้วใช่ไหม

ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า

ถัดไป: ต้นไม้ค้นหาแบบทวิภาคใน Python →

ฝึกด้วยโจทย์

ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI

โจทย์ทั้งหมด