เครื่องคำนวณการเรียงลำดับทอพอโลยี

คำนวณลำดับทอพอโลยีของกราฟแบบระบุทิศทางที่ไม่มีวงจร (DAG) โดยใช้อัลกอริทึมของ Kahn หรือ DFS ตรวจจับวงจร รายงานเส้นทางวงจร สร้างมุมมองเลเยอร์การประมวลผลแบบขนาน รองรับการเรียงลำดับตามตัวอักษร และแสดงภาพเคลื่อนไหวแต่ละขั้นตอนบนกราฟแบบโต้ตอบ

⚡ ลองใช้ตัวอย่าง:

ห่วงโซ่เชิงเส้น ลำดับการแต่งกาย วิชาบังคับก่อน กิจวัตรตอนเช้า เป้าหมายการ Build ตัวอย่างความประชิด แบบมีวงจร Pipeline DAG

รูปแบบการป้อนข้อมูล

→ รายการความประชิด

⧇ รายการความประชิด

ข้อมูลกราฟ

รูปแบบขอบ: A -> B (ยอมรับ →, =>, : ด้วย) สูงสุด 80 จุดยอด / 800 ขอบ

รูปแบบความประชิด: A: B, C, D — หนึ่งจุดยอดต่อบรรทัด ตามด้วยจุดยอดถัดไปโดยตรง

อัลกอริทึม

อัลกอริทึมของ Kahn (ตามพจนานุกรม) จะให้ลำดับที่ไม่ซ้ำกันและทำซ้ำได้ ส่วน DFS post-order เป็นวิธี depth-first แบบคลาสสิก

Embed เครื่องคำนวณการเรียงลำดับทอพอโลยี Widget

เกี่ยวกับ เครื่องคำนวณการเรียงลำดับทอพอโลยี

เครื่องคำนวณการเรียงลำดับทอพอโลยี คำนวณการจัดเรียงจุดยอดในเชิงเส้นของ กราฟระบุทิศทางที่ไม่มีวงจร (DAG) โดยที่ทุกขอบระบุทิศทางจาก u ไป v จะกำหนดให้ u อยู่ก่อน v ป้อนกราฟของคุณเป็นรายการขอบหรือรายการความประชิด และเครื่องมือจะคืนค่าลำดับทอพอโลยีโดยใช้อัลกอริทึมของ Kahn หรือ DFS post-order, ตรวจจับวงจร (พร้อมเส้นทางวงจรที่แน่นอน), จัดกลุ่มงานออกเป็นเลเยอร์การทำงานแบบขนาน, นับจำนวนการจัดเรียงที่ถูกต้อง และแสดงภาพเคลื่อนไหวแต่ละขั้นตอนบนกราฟแบบโต้ตอบ

การเรียงลำดับทอพอโลยีคืออะไร?

กำหนดให้กราฟระบุทิศทาง G = (V, E) การเรียงลำดับทอพอโลยี (หรือ topological ordering) คือการจัดเรียงจุดยอด v₁, v₂, …, vₙ ในเชิงเส้นเพื่อให้ทุกขอบระบุทิศทาง (u → v), u จะปรากฏก่อน v ในการจัดเรียง การเรียงลำดับทอพอโลยีจะมีอยู่ ก็ต่อเมื่อ กราฟไม่มีวงจรระบุทิศทาง — นั่นคือ กราฟต้องเป็น DAG การจัดเรียงมักจะไม่ซ้ำกันเพียงแบบเดียว: กราฟสามารถมีการเรียงลำดับทอพอโลยีที่ถูกต้องหลายแบบเมื่อมีจุดยอดหลายจุดที่มีระดับเข้าเป็นศูนย์ในเวลาเดียวกัน

นิยามการเรียงลำดับทอพอโลยี

การเรียงสับเปลี่ยน (v₁, v₂, …, v_n) ของ V จะเป็นทอพอโลยีก็ต่อเมื่อ
สำหรับทุกขอบ (u → v) ใน E: position(u) < position(v)

อัลกอริทึมที่ใช้ในเครื่องคำนวณนี้

อัลกอริทึมของ Kahn (ใช้ BFS, 1962)

อัลกอริทึมของ Kahn เป็นวิธีจัดเรียงทอพอโลยีที่เข้าใจง่ายที่สุด ในทุกขั้นตอนจะเลือกจุดยอดที่มี ระดับเข้าเป็นศูนย์ (ไม่มีขอบเข้า), ใส่จุดยอดนั้นในผลลัพธ์ และ "ลบ" มันออกจากกราฟโดยลดระดับเข้าของจุดยอดถัดไปแต่ละจุด เมื่อมีจุดยอดหลายจุดที่มีระดับเข้าเป็นศูนย์ การตัดสินใจเลือกสามารถใช้ min-heap (เพื่อให้ได้การเรียงลำดับที่ เล็กที่สุดตามพจนานุกรม) หรือคิวแบบ FIFO (เพื่อให้ได้ ลำดับตามการป้อน) อัลกอริทึมของ Kahn ทำงานในเวลา O(|V| + |E|) และทำหน้าที่เป็นตัวตรวจจับวงจรด้วย: หากจุดยอดใดยังมีระดับเข้า > 0 หลังจากคิวว่างเปล่า แสดงว่ากราฟมีวงจร

อัลกอริทึมของ Kahn (รหัสเทียม)

Kahn(G):
  Q ← { v ∈ V : indeg(v) = 0 }
  L ← [ ]
  ขณะที่ Q ไม่ว่าง:
    u ← Q.pop()
    L.append(u)
    สำหรับ แต่ละขอบ u → v:
      indeg(v) -= 1
      ถ้า indeg(v) = 0: Q.push(v)
  ถ้า |L| < |V|: รายงานวงจร
  มิฉะนั้น: คืนค่า L

DFS post-order (Tarjan, 1976)

อัลกอริทึม DFS จะรันการค้นหาตามแนวลึก และเมื่อใดก็ตามที่จุดยอด เสร็จสิ้น (นั่นคือ จุดยอดถัดไปทั้งหมดได้รับการสำรวจครบแล้ว) จุดยอดนั้นจะถูกผลักลงในสแต็ก การกลับลำดับสแต็กในตอนท้ายจะได้ลำดับทอพอโลยีที่ถูกต้อง การตรวจจับวงจรเป็นไปอย่างธรรมชาติ: การพบจุดยอดที่ยัง อยู่ระหว่างดำเนินการ (ทำเครื่องหมายสีเทา) หมายความว่าพบขอบย้อนกลับ ดังนั้นกราฟจึงไม่ใช่ DAG อัลกอริทึม DFS post-order ทำงานในเวลา O(|V| + |E|) เช่นกัน

DFS post-order (รหัสเทียม)

DFS-Topo(G):
  สำหรับ แต่ละจุดยอด u ใน V: color[u] ← WHITE
  L ← สแต็กว่าง
  สำหรับ แต่ละจุดยอด u ใน V:
    ถ้า color[u] = WHITE: visit(u)
  คืนค่า reverse(L)

visit(u):
  color[u] ← GRAY
  สำหรับ แต่ละขอบ u → v:
    ถ้า color[v] = GRAY: รายงานวงจร
    ถ้า color[v] = WHITE: visit(v)
  color[u] ← BLACK; L.push(u)

เลเยอร์การทำงานแบบขนาน

มุมมอง แบบเลเยอร์ ของ DAG จะแบ่งพาร์ทิชันจุดยอดออกเป็นระดับต่างๆ เพื่อให้ทุกขอบชี้จากระดับที่ต่ำกว่าไปยังระดับที่สูงกว่า จุดยอดในเลเยอร์เดียวกันเป็นอิสระต่อกัน ดังนั้นจึงสามารถทำงานขนานกันได้ จำนวนเลเยอร์จะเท่ากับความยาวของเส้นทางที่ยาวที่สุดบวกหนึ่ง — นี่คือ เส้นทางวิกฤต (critical path) ของ DAG ซึ่งเป็นจำนวนรอบขั้นต่ำที่จำเป็นในการทำงานทั้งหมดให้เสร็จสิ้นแม้จะมีการทำงานแบบขนานไม่จำกัดก็ตาม เครื่องคำนวณนี้จะสร้างมุมมองเลเยอร์โดยอัตโนมัติเมื่อข้อมูลที่ป้อนเป็น DAG

การตรวจจับวงจร

หากกราฟมีวงจรระบุทิศทาง จะไม่สามารถจัดเรียงทอพอโลยีได้ เครื่องคำนวณของเราจะรายงานเส้นทางวงจรที่แน่นอน (เช่น A → B → C → A) และไฮไลต์ขอบของวงจรเป็นสีแดงบนการแสดงภาพ การลบขอบเพียงขอบเดียวในวงจรก็เพียงพอที่จะทำให้กราฟกลับมาไม่มีวงจรได้

รูปแบบการป้อนข้อมูล

รายการขอบ (Edge list)

เขียนแต่ละขอบระบุทิศทางเป็น ต้นทาง -> ปลายทาง คั่นด้วยจุลภาคหรือขึ้นบรรทัดใหม่ รูปแบบลูกศรที่ยอมรับ: ->, →, =>, -->, : คุณยังสามารถเขียนขอบเชื่อมต่อกันได้: A -> B -> C เป็นตัวย่อของ A->B และ B->C ป้ายชื่อจุดยอดสามารถเป็นตัวอักษร ตัวเลข ขีดล่าง ขีดกลาง และจุด

A -> B, B -> C, A -> C
C -> D
Shirt -> Tie -> Jacket

รายการความประชิด (Adjacency list)

เขียนแต่ละจุดยอด ตามด้วยเครื่องหมายทวิภาค (:) และ จุดยอดถัดไป (จุดยอดที่มันชี้ไป) จุดยอดที่ไม่มีจุดยอดถัดไปก็ยังต้องมีบรรทัดของตัวเอง เช่น D:

A: B, C
B: D
C: D
D:

วิธีใช้เครื่องคำนวณนี้

เลือกรูปแบบ: สลับระหว่างรายการขอบและรายการความประชิดด้วยปุ่มตัวเลือก
ป้อนข้อมูลกราฟ: วางข้อมูลของคุณหรือคลิกตัวอย่างด่วน (ลำดับการแต่งตัว, วิชาบังคับก่อน, เป้าหมายการ build, กราฟที่มีวงจร และอื่นๆ)
เลือกอัลกอริทึม: Kahn (ตามพจนานุกรม) สำหรับลำดับที่ไม่ซ้ำกันและทำซ้ำได้, ลำดับการป้อนเพื่อคงลำดับการป้อนข้อมูล, DFS post-order สำหรับวิธีตามแนวลึกแบบคลาสสิก หรือเลือก แสดงทั้งหมด เพื่อดูการจัดเรียงทุกแบบเปรียบเทียบกัน
คลิก "จัดเรียงทอพอโลยี": ลำดับ, การตรวจจับวงจร, มุมมองเลเยอร์, ความยาวเส้นทางวิกฤต, จำนวนการจัดเรียงที่ถูกต้องทั้งหมด และกราฟแบบโต้ตอบจะปรากฏด้านล่าง
สำรวจ: กด Play เพื่อดูจุดยอดแต่ละจุดถูกปล่อยออกมาทีละขั้นตอน ป้ายระดับเข้าจะอัปเดตแบบสด คุณสามารถลากจุดยอดเพื่อจัดวางผังใหม่ได้

การประยุกต์ใช้ในโลกแห่งความเป็นจริง

ระบบการ Build และคอมไพเลอร์

เครื่องมืออย่าง make, Bazel, Gradle และ npm จะจัดเรียงทอพอโลยีของเป้าหมายการ Build เพื่อให้แต่ละเป้าหมายถูกคอมไพล์หลังจากพึ่งพาทั้งหมดเสร็จสิ้นแล้วเท่านั้น วงจรในกราฟการพึ่งพามักจะรายงานว่าเป็นข้อผิดพลาดร้ายแรง เนื่องจากระบบการ Build ไม่สามารถตัดสินใจได้ว่าจะเริ่มจากจุดไหน

การจัดตารางงาน

ผู้จัดการโครงการใช้ DAG เพื่อบันทึกการพึ่งพางาน การเรียงลำดับทอพอโลยีจะให้ลำดับการปฏิบัติงานที่ถูกต้อง และมุมมองเลเยอร์จะให้จำนวนรอบขั้นต่ำภายใต้การทำงานแบบขนานไม่จำกัด ห่วงโซ่ที่ยาวที่สุดคือ เส้นทางวิกฤต ที่กำหนดระยะเวลาของโครงการ

การวางแผนวิชาบังคับก่อน

แค็ตตาล็อกรายวิชาของมหาวิทยาลัยคือ DAG: ขอบคือความสัมพันธ์ของวิชาบังคับก่อน ลำดับทอพอโลยีคือแผนการเรียนที่ถูกต้อง และเลเยอร์จะบอกนักศึกษาว่ากลุ่มวิชาใดที่สามารถเรียนขนานกันได้ในแต่ละภาคการศึกษา

การคำนวณสเปรดชีตใหม่

เมื่อเซลล์มีการเปลี่ยนแปลง สเปรดชีตต้องคำนวณเซลล์ปลายทางใหม่ตามลำดับการพึ่งพา — ซึ่งก็คือการเรียงลำดับทอพอโลยีของ DAG การพึ่งพาเซลล์ การอ้างอิงแบบวงกลม (วงจร) จะถูกปฏิเสธโดยแอปพลิเคชัน

ตัวจัดการแพ็กเกจและตัวโหลดปลั๊กอิน

Apt, pip, Homebrew, Maven และเฟรมเวิร์กปลั๊กอินนับไม่ถ้วนจะแก้ไขลำดับการติดตั้งหรือโหลดโดยการเรียงลำดับทอพอโลยีของ DAG การพึ่งพา

การแก้สัญลักษณ์และการจัดตารางคำสั่ง

คอมไพเลอร์ใช้การจัดเรียงทอพอโลยีเพื่อจัดลำดับการประกาศ และ CPU ใช้ DAG การพึ่งพาข้อมูลเพื่อจัดตารางคำสั่งใน reorder buffer โดยไม่ละเมิดอันตรายของข้อมูล (data hazards)

การนับจำนวนการจัดเรียงทอพอโลยี

สำหรับ DAG ที่มี n จุดยอด จำนวนการจัดเรียงทอพอโลยีที่แตกต่างกันและถูกต้องอาจมีตั้งแต่ 1 (สำหรับห่วงโซ่ที่เรียงลำดับทั้งหมด) ไปจนถึง n! (สำหรับกราฟที่ไม่มีขอบ) การคำนวณจำนวนที่แน่นอนนั้นเป็นปัญหาแบบ #P-complete โดยทั่วไป แต่สำหรับกราฟที่มีจุดยอดไม่เกิน 16 จุด เครื่องคำนวณนี้จะแจงนับพวกมันโดยใช้สูตร bitmask dynamic-programming: f(S) = Σ f(S ∪ {v}) สำหรับทุก v ∉ S ที่มีจุดยอดก่อนหน้าทั้งหมดอยู่ใน S

ความซับซ้อนและประสิทธิภาพ

เวลา: ทั้งอัลกอริทึมของ Kahn และ DFS post-order รันในเวลา O(|V| + |E|) — เป็นเชิงเส้นตามขนาดของกราฟ
พื้นที่: O(|V|) สำหรับการติดตามระดับเข้าและลำดับผลลัพธ์ บวกกับ O(|V| + |E|) สำหรับโครงสร้างความประชิด
การตรวจจับวงจร: มีอยู่ในทั้งสองอัลกอริทึม Kahn ตรวจพบวงจรเมื่อ |ผลลัพธ์| < |V| ส่วน DFS ตรวจพบเมื่อพบขอบย้อนกลับ (เพื่อนบ้านสีเทา)
ขีดจำกัดในเครื่องมือนี้: สูงสุด 80 จุดยอดและ 800 ขอบสำหรับการแสดงภาพแบบโต้ตอบ การนับการจัดเรียงจำกัดที่ 16 จุดยอด

คำถามที่พบบ่อย

การเรียงลำดับทอพอโลยีคืออะไร?

การเรียงลำดับทอพอโลยีของกราฟระบุทิศทางที่ไม่มีวงจร คือการจัดเรียงจุดยอดในเชิงเส้นโดยที่ทุกขอบระบุทิศทางจาก u ไป v จะทำให้ u อยู่ก่อน v มันแสดงถึงลำดับที่ถูกต้องในการประมวลผลงานโดยเคารพการพึ่งพาของงานเหล่านั้น

เครื่องคำนวณนี้ใช้อัลกอริทึมใด?

เครื่องคำนวณรันทั้งอัลกอริทึมของ Kahn และ DFS post-order อัลกอริทึมของ Kahn จะลบจุดยอดที่มีระดับเข้าเป็นศูนย์ซ้ำๆ และลดระดับเข้าของจุดยอดถัดไป ส่วน DFS post-order จะรันการค้นหาตามแนวลึกและกลับลำดับการเสร็จสิ้น ทั้งสองรันในเวลา O(|V| + |E|)

จะเกิดอะไรขึ้นถ้ากราฟของฉันมีวงจร?

กราฟที่มีวงจรระบุทิศทางจะไม่มีการเรียงลำดับทอพอโลยี เครื่องคำนวณจะตรวจจับวงจร ไฮไลต์เป็นสีแดงบนการแสดงภาพ และรายงานเส้นทางวงจรที่แน่นอน เพื่อให้คุณเห็นว่าควรลบขอบใดเพื่อให้กราฟกลายเป็น DAG

การเรียงลำดับทอพอโลยีที่เล็กที่สุดตามพจนานุกรมคืออะไร?

เมื่อมีการเรียงลำดับทอพอโลยีหลายแบบที่ถูกต้อง แบบที่เล็กที่สุดตามพจนานุกรมจะได้มาจากการเลือกจุดยอดที่เล็กที่สุดตามตัวอักษรที่มีระดับเข้าเป็นศูนย์ในแต่ละขั้นตอนเสมอ โหมด Kahn เริ่มต้นของเครื่องคำนวณนี้จะคืนค่าการเรียงลำดับที่ไม่ซ้ำกันนี้ ซึ่งมีความเสถียรและทำซ้ำได้ง่าย

มุมมองเลเยอร์หรือระดับคืออะไร?

มุมมองเลเยอร์จะจัดกลุ่มจุดยอดตามความยาวเส้นทางที่ยาวที่สุดจากแหล่งกำเนิดใดๆ จุดยอดในเลเยอร์เดียวกันไม่มีการพึ่งพากัน ดังนั้นจึงสามารถรันแบบขนานได้ จำนวนเลเยอร์จะเท่ากับความยาวห่วงโซ่การพึ่งพาที่ยาวที่สุดบวกหนึ่ง และให้จำนวนรอบขั้นต่ำที่จำเป็นในการทำงานทั้งหมดให้เสร็จสิ้น

กราฟหนึ่งสามารถมีการเรียงลำดับทอพอโลยีที่ถูกต้องหลายแบบได้หรือไม่?

ได้ หากในขั้นตอนใดก็ตาม อัลกอริทึมของ Kahn มีจุดยอดหลายจุดที่มีระดับเข้าเป็นศูนย์ สามารถเลือกจุดใดก็ได้เป็นลำดับถัดไป เครื่องคำนวณนี้นับจำนวนการเรียงลำดับทอพอโลยีที่แตกต่างกันที่แน่นอนสำหรับกราฟที่มีจุดยอดไม่เกิน 16 จุด

ความแตกต่างระหว่างอัลกอริทึมของ Kahn และ DFS post-order คืออะไร?

Kahn ทำงานแบบบนลงล่าง: จะเลือกแหล่งกำเนิด (ระดับเข้า 0) ซ้ำๆ และปล่อยออกมาเป็นอันดับแรกๆ ส่วน DFS post-order ทำงานแบบล่างขึ้นบน: จะทำจุดปลายทางให้เสร็จก่อนแล้วจึงเติมไว้ด้านหน้าลำดับ ทั้งสองมีประสิทธิภาพ O(|V| + |E|) และให้ลำดับทอพอโลยีที่ถูกต้อง แต่อาจให้ลำดับที่แตกต่างกัน Kahn จัดการแบบขนานและการเรียงตามพจนานุกรมได้ง่ายกว่า ส่วน DFS รวมเข้ากับการวิเคราะห์อื่นๆ เช่น ส่วนประกอบที่เชื่อมกันอย่างแข็งแกร่ง (SCC) ได้ง่ายกว่า

ขนาดกราฟสูงสุดที่เครื่องมือนี้รองรับคือเท่าใด?

เครื่องคำนวณรองรับจุดยอดสูงสุด 80 จุด และขอบ 800 ขอบ การนับจำนวนการเรียงลำดับทอพอโลยีทั้งหมดจำกัดอยู่ที่ 16 จุดยอด เนื่องจากปัญหานี้เป็นแบบ #P-complete และพื้นที่สถานะเติบโตเป็น 2ⁿ การแสดงภาพแบบโต้ตอบและภาพเคลื่อนไหวอัลกอริทึมจะทำงานได้อย่างราบรื่นจนถึงขนาดสูงสุด