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

Question

IT Interview Practice · Accepted Answer

**การเรียงลำดับโทโพโลยี** จัดเรียงจุดยอดของ **DAG** (กราฟแบบไม่มีวงจร) เป็นลำดับเชิงเส้น เพื่อให้แต่ละขอบ u->v มี u **ก่อน** v ตอบคำถาม "ฉันสามารถทำงานเหล่านี้ตามลำดับใดได้บ้างเมื่อพิจารณาจากความสัมพันธ์ของพวกเขา?"

## แนวคิด

สองวิธีทั่วไป: **อัลกอริทึมของ Kahn** (ลบโหนดที่มีดีกรีเข้า 0 ซ้ำๆ) หรือ **DFS** (ลำดับหลังที่กลับด้าน) ลำดับที่ถูกต้องมีอยู่ **เฉพาะเมื่อไม่มีวงจร**

## ตัวอย่าง (อัลกอริทึมของ Kahn)

```python
from collections import deque

def topo_sort(graph):
    indeg = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1                 # count incoming edges
    queue = deque([u for u in indeg if indeg[u] == 0])
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1                 # "remove" the edge
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == len(graph) else None  # None -> cycle

topo_sort({'shirt': ['tie'], 'tie': ['jacket'], 'jacket': []})
# -> ['shirt', 'tie', 'jacket']
```

## ความซับซ้อน

- **เวลา:** O(V + E) **พื้นที่:** O(V)

## เมื่อใช้ / ข้อควรระวัง

ใช้สำหรับ **ระบบการสร้าง** การจัดตารางงาน ข้อกำหนดเบื้องต้นของหลักสูตร และการแก้ไขความสัมพันธ์ หากผลลัพธ์สั้นกว่า V กราฟมี **วงจร** (ไม่มีลำดับที่ถูกต้อง) โดยทั่วไป **ลำดับนั้นไม่ซ้ำกัน**

## ทำไมจึงสำคัญ

การจัดลำดับความสัมพันธ์มีอยู่ทุกที่ — ตัวแปลภาษา ตัวจัดการแพกเกจ การคำนวณใหม่สเปรดชีต ไปป์ไลน์ CI

การเรียงลำดับโทโพโลยีทำหน้าที่เป็นตัวตรวจจับวงจรสำหรับกราฟแบบมีทิศทางด้วย

การรับรู้ปัญหาว่า "ลำดับภายใต้ข้อจำกัด" และหยิบการเรียงลำดับโทโพฯ ถือเป็นสัญญาณที่แข็งแกร่งสำหรับผู้พัฒนาอาวุโส

แนวคิด

ตัวอย่าง (อัลกอริทึมของ Kahn)

ความซับซ้อน

เมื่อใช้ / ข้อควรระวัง

ทำไมจึงสำคัญ

คำถามที่เกี่ยวข้อง