DFS การเรียกซ้ำ และสแตกแบบวนซ้ำ
สำรวจให้ลึกและหลีกเลี่ยงขีดจำกัดการเรียกซ้ำ
DFS การเรียกซ้ำ และสแตกแบบวนซ้ำ เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
DFS ทำอะไร
DFSจะลงลึกไปตามเส้นทางหนึ่งให้ไกลที่สุด จากนั้นย้อนกลับและลองเส้นทางถัดไป ลองนึกภาพการสำรวจทางเดินในเขาวงกตทีละทาง 🧭
DFS เทียบกับ BFS
BFS แผ่ขยายเป็นชั้น ๆ ส่วนDFSจะลงลึกก่อน ทั้งสองวิธีเยี่ยมชมโหนดที่ไปถึงได้ทุกโหนด แต่มีลำดับการเยี่ยมชมที่แตกต่างกันมาก
รูปแบบการเรียกซ้ำ
DFS แบบเรียกซ้ำจะทำเครื่องหมายโหนดว่าเยี่ยมชมแล้ว จากนั้นเรียกตัวเองกับเพื่อนบ้านแต่ละตัวที่ยังไม่เคยเยี่ยมชม สแตกการเรียกจะจดจำตำแหน่งที่จะย้อนกลับไป
def dfs(u):
visited[u] = True
for v in adj[u]:
if not visited[v]:
dfs(v)ทำเครื่องหมายก่อนเรียกซ้ำ
กำหนดค่าเยี่ยมชมแล้วเมื่อเข้าสู่โหนด ก่อนสำรวจเพื่อนบ้าน หากไม่ทำเช่นนั้น วงจรจะทำให้ DFS เรียกซ้ำไม่รู้จบ
กับดักข้อจำกัดการเรียกซ้ำ
Python จำกัดการเรียกซ้ำไว้ประมาณ 1,000 ครั้ง กราฟที่ลึกมากจะทำให้เกิด RecursionError ซึ่งปรากฏเป็นผลตัดสินว่ามีข้อผิดพลาดขณะทำงาน
เพิ่มขีดจำกัด
วิธีแก้ด่วนคือเพิ่มขีดจำกัดด้วย setrecursionlimit กำหนดค่าให้สูงกว่าความลึกสูงสุดที่อาจเกิดขึ้นก่อนเริ่มทำงาน DFS
import sys
sys.setrecursionlimit(300000)เปลี่ยนไปใช้แบบวนซ้ำ
วิธีแก้ที่ปลอดภัยที่สุดคือใช้ DFS แบบวนซ้ำร่วมกับสแตกของคุณเอง เมื่อไม่มีความลึกของการเรียก ก็จะไม่มีการล่มจากการเรียกซ้ำ
stack = [start]นำสมาชิกออกจากสแตกด้วย pop
ในแต่ละขั้น ให้ใช้ pop นำสมาชิกด้านบนสุดของสแตกออก หลักการเข้าหลังออกก่อนทำให้ DFS ลงลึกไปตามเส้นทางล่าสุดก่อน
u = stack.pop()ใส่เพื่อนบ้านลงสแตก
หลังจากนำ u ออกแล้ว ให้ใส่เพื่อนบ้านแต่ละตัวที่ยังไม่เคยเยี่ยมชมลงในสแตก และทำเครื่องหมายเพื่อไม่ให้ใส่ซ้ำ
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)ลูปแบบวนซ้ำฉบับเต็ม
ทำซ้ำการนำสมาชิกออกและใส่สมาชิกเข้าไปขณะที่สแตกยังมีโหนดอยู่ เมื่อสแตกว่างเปล่า โหนดทุกโหนดที่ไปถึงได้จะถูกเยี่ยมชมแล้ว
while stack:
u = stack.pop()
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)ใช้ต้นทุนเท่ากับ BFS
เช่นเดียวกับ BFS, DFS เยี่ยมชมโหนดและเส้นเชื่อมแต่ละรายการเพียงครั้งเดียว จึงทำงานในเวลา O(n + m) เลือกใช้ตามลำดับที่เหมาะกับโจทย์
ตรวจสอบอย่างรวดเร็ว
DFS แบบเรียกซ้ำของคุณล่มเมื่อเจอกราฟที่ลึกมาก เหตุใดจึงเป็นเช่นนั้น
ทบทวน
คุณสามารถใช้ DFS แบบเรียกซ้ำหรือใช้สแตกของคุณเอง ทำเครื่องหมายว่าเยี่ยมชมแล้วเมื่อเข้าสู่โหนด และเปลี่ยนเป็นแบบวนซ้ำเมื่อกราฟมีความลึกมาก 🎉
คำถามที่พบบ่อย
บทเรียน “DFS การเรียกซ้ำ และสแตกแบบวนซ้ำ” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “DFS การเรียกซ้ำ และสแตกแบบวนซ้ำ” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “DFS การเรียกซ้ำ และสแตกแบบวนซ้ำ”
สำรวจให้ลึกและหลีกเลี่ยงขีดจำกัดการเรียกซ้ำ คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “DFS การเรียกซ้ำ และสแตกแบบวนซ้ำ” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- สร้างรายการประชิดจากข้อมูลเข้า
- BFS สำหรับพาธสั้นที่สุดแบบไม่มีน้ำหนัก
- DFS การเรียกซ้ำ และสแตกแบบวนซ้ำ
- องค์ประกอบที่เชื่อมต่อกันและการเติมพื้นที่