ตรวจจับวัฏจักรในกราฟมีทิศทาง
ระบายสีโหนดเพื่อค้นหาเส้นย้อนกลับ
ตรวจจับวัฏจักรในกราฟมีทิศทาง เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
เหตุใดวัฏจักรจึงสำคัญ
วัฏจักรแบบมีทิศทางหมายความว่าข้อกำหนดการพึ่งพาวนกลับมาหากันเอง การตรวจพบวัฏจักรทำให้ทราบว่าจะไม่มีลำดับทอพอโลยีหรือตารางงานที่ถูกต้อง
กราฟไม่มีทิศทางนั้นต่างออกไป
การตรวจจับวัฏจักรในที่นี้เกี่ยวข้องกับทิศทาง การเดินตามเส้นเชื่อมผิดทิศไม่นับ ดังนั้นเทคนิคของกราฟไม่มีทิศทางจึงใช้ไม่ได้
แนวคิดสามสี
กำหนดสีหนึ่งในสามสีให้แต่ละโหนด: สีขาวหมายถึงยังไม่เคยเยี่ยมชม สีเทาหมายถึงกำลังประมวลผล และสีดำหมายถึงประมวลผลเสร็จสมบูรณ์แล้ว
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * nสีเทาหมายถึงอยู่บนสแตก
โหนดสีเทาอยู่บนเส้นทาง DFS ปัจจุบันของคุณ คุณเข้ามาถึงโหนดนี้แล้ว แต่ยังสำรวจโหนดลูกหลานทั้งหมดไม่เสร็จ
เข้าไปยังโหนด
เมื่อ DFS ไปถึงโหนด ให้ทำเครื่องหมายเป็นสีเทาก่อนสำรวจ การทำเช่นนี้ระบุว่าโหนดเป็นส่วนหนึ่งของเส้นทางที่กำลังดำเนินการ
def dfs(u):
color[u] = GRAYสัญญาณจากเส้นเชื่อมย้อนกลับ
หากคุณไปถึงโหนดข้างเคียงที่เป็นสีเทาอยู่แล้ว แสดงว่าพบเส้นเชื่อมย้อนกลับเข้าสู่เส้นทางปัจจุบัน นั่นคือวัฏจักร
for v in adj[u]:
if color[v] == GRAY:
return True # cycleเรียกซ้ำเข้าไปยังโหนดสีขาว
โหนดข้างเคียงสีขาวยังไม่เคยถูกสำรวจ จึงให้เรียกซ้ำเข้าไป หากการเรียกที่ลึกลงไปรายงานว่าพบวัฏจักร ให้ส่งค่าจริงย้อนกลับทันที
elif color[v] == WHITE and dfs(v):
return Trueสีดำปลอดภัย
โหนดข้างเคียงสีดำถูกสำรวจครบแล้วและไม่มีวัฏจักร คุณจึงไม่ต้องสนใจโหนดนั้น การกลับไปเยี่ยมชมอีกครั้งมีแต่จะเสียเวลา
เสร็จสิ้นการประมวลผลโหนด
หลังจากจัดการโหนดข้างเคียงทั้งหมดแล้ว ให้ทำเครื่องหมายโหนดเป็นสีดำ โหนดนั้นจะออกจากเส้นทางที่กำลังดำเนินการและถูกทำเครื่องหมายว่าเสร็จสมบูรณ์
color[u] = BLACK
return Falseครอบคลุมทุกองค์ประกอบ
กราฟอาจไม่เชื่อมต่อกัน ดังนั้นให้เริ่ม DFS จากโหนดที่ยังเป็นสีขาวทุกโหนด เพื่อให้แน่ใจว่าตรวจสอบกราฟครบทั้งหมด
if any(color[u]==WHITE and dfs(u) for u in range(n)):
print('cycle')ระวังขีดจำกัดการเรียกซ้ำ
กราฟที่ลึกมากอาจทำให้สแตกการเรียกซ้ำของ Python ล้นได้ ให้เพิ่มขีดจำกัด หรือเขียน DFS ใหม่โดยใช้สแตกที่จัดการเอง
import sys
sys.setrecursionlimit(300000)ตรวจสอบความเข้าใจ
ระหว่างทำ DFS คุณไปถึงโหนดข้างเคียงที่เป็นสีเทาอยู่ในขณะนั้น คุณเพิ่งพบสิ่งใด
ทบทวน: การตรวจจับวัฏจักร
ระบายสีโหนดเป็นสีขาว สีเทา แล้วจึงเป็นสีดำ โหนดข้างเคียงสีเทาระหว่างทำ DFS คือเส้นเชื่อมย้อนกลับ ซึ่งพิสูจน์ว่ามีวัฏจักรแบบมีทิศทาง 🔁
คำถามที่พบบ่อย
บทเรียน “ตรวจจับวัฏจักรในกราฟมีทิศทาง” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “ตรวจจับวัฏจักรในกราฟมีทิศทาง” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “ตรวจจับวัฏจักรในกราฟมีทิศทาง”
ระบายสีโหนดเพื่อค้นหาเส้นย้อนกลับ คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน
บทเรียน “ตรวจจับวัฏจักรในกราฟมีทิศทาง” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- การเรียงลำดับเชิงทอพอโลยีด้วยอัลกอริทึมของ Kahn
- ตรวจจับวัฏจักรในกราฟมีทิศทาง
- องค์ประกอบเชื่อมโยงอย่างแน่นแฟ้น
- สะพานและจุดตัด