การค้นหาแนวลึก DFS ใน Python
DFS ใช้ recursion หรือ stack ที่กำหนดเอง
การค้นหาแนวลึก DFS ใน Python คืออะไร?
DFS ใช้ recursion หรือ stack ที่กำหนดเอง
สำรวจเส้นทางให้ลึกก่อนย้อนกลับ
ควรใช้เมื่อใด?
- ทำความเข้าใจอัลกอริทึมและโครงสร้างข้อมูล
- สังเกตแต่ละขั้นตอนและกรณีขอบ
- เปรียบเทียบเวลาและหน่วยความจำ
ภาพจำลอง การค้นหาแนวลึก 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"))ผลลัพธ์ที่คาดหวัง
['A', 'B', 'D', 'C', 'E']หลักการทำงาน
แต่ละ vertex และ edge ถูกประมวลผลไม่เกินหนึ่งครั้ง จึงเป็น O(V+E)
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัด
ลองเปลี่ยน input และทดสอบกรณีขอบก่อนใช้ชุดข้อมูลที่ใหญ่ขึ้น
- ทดสอบ input ว่าง หนึ่งสมาชิก และค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นตอน
- เปรียบเทียบประสิทธิภาพกับวิธีอื่น