การเรียงลำดับเชิงทอพอโลยีด้วยอัลกอริทึมของ Kahn
จัดลำดับงานที่พึ่งพางานอื่น
การเรียงลำดับเชิงทอพอโลยีด้วยอัลกอริทึมของ Kahn เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
ลำดับทอพอโลยีคืออะไร
ลำดับทอพอโลยี จะแสดงโหนดทุกโหนดของกราฟมีทิศทาง โดยให้เส้นเชื่อมแต่ละเส้นชี้จากโหนดก่อนหน้าไปยังโหนดถัดไป ลองนึกถึงการจัดงานที่ต้องทำงานหนึ่งก่อนงานที่ต้องพึ่งพางานนั้น
ใช้ได้เฉพาะ DAG
วิธีนี้ใช้ได้เฉพาะกับ DAG หรือกราฟมีทิศทางแบบไม่มีวัฏจักรเท่านั้น หากมีวัฏจักรอยู่ จะไม่มีลำดับที่ถูกต้องซึ่งทำให้ข้อกำหนดการพึ่งพาทุกข้อเป็นจริงได้
แนวคิดเรื่องดีกรีขาเข้า
อัลกอริทึมของ Kahn อาศัยแนวคิดเรื่องดีกรีขาเข้า: จำนวนเส้นเชื่อมที่ชี้เข้าสู่โหนดหนึ่ง โหนดที่มีดีกรีขาเข้าเป็นศูนย์ไม่มีข้อกำหนดที่ยังไม่ได้ทำ
นับดีกรีขาเข้าทุกโหนด
รอบแรก: เดินดูเส้นเชื่อมทั้งหมดและ นับ ว่าแต่ละโหนดเป็นจุดหมายกี่ครั้ง ค่านี้จะเป็นดีกรีขาเข้าของแต่ละโหนด
indeg = [0] * n
for u in range(n):
for v in adj[u]:
indeg[v] += 1เริ่มต้นคิวของโหนดที่พร้อม
โหนดทุกโหนดที่มีดีกรีขาเข้าเป็นศูนย์พร้อมใช้งานทันที ดังนั้นให้ใส่โหนดเหล่านี้ทั้งหมดลงในคิวเพื่อเริ่มต้น
from collections import deque
q = deque(u for u in range(n) if indeg[u] == 0)ประมวลผลทีละโหนด
นำโหนดที่พร้อมออกจากคิวแล้ว append ลงในลำดับของคุณ ตอนนี้โหนดนี้ปลอดภัยที่จะจัดวาง เพราะไม่มีงานที่เหลือต้องพึ่งพาโหนดนี้
u = q.popleft()
order.append(u)ปลดล็อกโหนดข้างเคียง
สำหรับโหนดข้างเคียงแต่ละโหนด ให้ลดดีกรีขาเข้าลงหนึ่ง เมื่อดีกรีขาเข้าของโหนดข้างเคียงเป็น ศูนย์ โหนดนั้นจะพร้อมใช้งานและเข้าคิว
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)ทำซ้ำจนกว่าคิวจะว่าง
ทำการนำโหนดออกจากคิวและปลดล็อกโหนดข้างเคียงต่อไปจนกว่าคิวจะว่าง ลำดับจะเพิ่มโหนดที่ปลอดภัยทีละโหนดจนจัดวางครบทุกโหนด
ตรวจจับวัฏจักรได้โดยไม่ต้องเพิ่มงาน
หากลำดับสุดท้ายมีโหนดน้อยกว่า n โหนด แสดงว่ามีวัฏจักรกักโหนดที่เหลือไว้ อัลกอริทึมของ Kahn จึงตรวจจับวัฏจักรได้โดยไม่ต้องเสียค่าใช้จ่ายเพิ่มเติม
if len(order) < n:
print('cycle exists')เวลาการทำงาน
แต่ละโหนดและเส้นเชื่อมถูกเยี่ยมชมหนึ่งครั้ง ดังนั้นอัลกอริทึมของ Kahn จึงทำงานในเวลา O(V + E) และรองรับกราฟที่มีเส้นเชื่อมหลายล้านเส้นได้
มีลำดับที่ถูกต้องได้หลายแบบ
เมื่อมีโหนดหลายโหนดพร้อมใช้งานในเวลาเดียวกัน คุณสามารถเลือกโหนดใดก็ได้ให้เป็นโหนดถัดไป ดังนั้น DAG จึงมักมีลำดับทอพอโลยีที่ถูกต้อง หลาย แบบ ไม่ใช่แค่แบบเดียว
ตรวจสอบความเข้าใจ
คุณทำอัลกอริทึมของ Kahn จบแล้ว แต่ลำดับมีโหนดน้อยกว่า n โหนด นั่นหมายความว่าอย่างไร
ทบทวน: อัลกอริทึมของ Kahn
นับดีกรีขาเข้า ใส่โหนดที่มีค่าเป็นศูนย์ลงในคิว นำโหนดออกจากคิว ลดค่าของโหนดข้างเคียง แล้วทำซ้ำ นี่คือการเรียงลำดับทอพอโลยีที่เรียบง่ายในเวลา O(V+E) 🚀
คำถามที่พบบ่อย
บทเรียน “การเรียงลำดับเชิงทอพอโลยีด้วยอัลกอริทึมของ Kahn” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “การเรียงลำดับเชิงทอพอโลยีด้วยอัลกอริทึมของ Kahn” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “การเรียงลำดับเชิงทอพอโลยีด้วยอัลกอริทึมของ Kahn”
จัดลำดับงานที่พึ่งพางานอื่น คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน
บทเรียน “การเรียงลำดับเชิงทอพอโลยีด้วยอัลกอริทึมของ Kahn” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- การเรียงลำดับเชิงทอพอโลยีด้วยอัลกอริทึมของ Kahn
- ตรวจจับวัฏจักรในกราฟมีทิศทาง
- องค์ประกอบเชื่อมโยงอย่างแน่นแฟ้น
- สะพานและจุดตัด