Topological Sort for Dependency Ordering
آمادگی مصاحبهٔ الگوریتمی با Python
- In 75 minutes, recognize directed prerequisite constraints and distinguish a valid dependency order from numerical sorting or shortest paths.
- Define indegree and the directed acyclic graph requirement; explain that multiple valid orders may exist.
- Independently choose edge direction and initial available tasks for a dependency-ordering problem.
- Develop the solution from testing candidate permutations to repeated full scans, then to a Python queue-based indegree algorithm.
- Prove that every queued vertex has no remaining unmet prerequisite and that processing fewer than all vertices detects a directed cycle.
- Derive O(V + E) time and O(V + E) total auxiliary storage including the adjacency representation.
- Test disconnected tasks, isolated vertices, self-loops, multiple valid orders, and repeated edges; keep adjacency and indegree duplicate handling consistent.
ترتیب کارها از روی پیشنیازها
```svg
<svg viewBox="0 0 800 450" xmlns="http://www.w3.org/2000/svg"><defs><marker id="arrow" markerWidth="10" markerHeight="10" refX="8" refY="5" orient="auto"><path class="tm-arrow" d="M0 0 L8 5 L0 10 Z"/></marker></defs><path class="tm-line-accent" d="M119 102 L269 142 M119 198 L269 158" stroke-width="2" marker-end="url(#arrow)"/><circle class="tm-soft" cx="90" cy="95" r="28"/><circle class="tm-soft" cx="90" cy="205" r="28"/><circle class="tm-soft" cx="300" cy="150" r="28"/><circle class="tm-soft" cx="300" cy="245" r="28"/><g font-size="24" text-anchor="middle"><text class="tm-text" x="90" y="103">0</text><text class="tm-text" x="90" y="213">1</text><text class="tm-text" x="300" y="158">2</text><text class="tm-text" x="300" y="253">3</text></g><text class="tm-muted" font-size="17" x="350" y="251" direction="rtl">مستقل</text><text class="tm-text-accent" font-size="18" x="205" y="40" text-anchor="middle" direction="rtl">پیکان از پیشنیاز به کار</text><rect class="tm-surface" x="440" y="55" width="320" height="155" rx="14"/><text class="tm-text" font-size="19" x="600" y="87" text-anchor="middle" direction="rtl">جفت ورودی: (کار، پیشنیاز)</text><text class="tm-text-accent" font-size="24" x="600" y="130" text-anchor="middle">(2, 0) (2, 1)</text><text class="tm-muted" font-size="17" x="600" y="169" text-anchor="middle" direction="rtl">هر ترتیب معتبر پذیرفته است</text><text class="tm-muted" font-size="17" x="600" y="195" text-anchor="middle" direction="rtl">ناممکن: None</text><rect class="tm-green" x="60" y="300" width="680" height="44" rx="10"/><text class="tm-text" font-size="23" x="260" y="330" text-anchor="middle">0 → 1 → 2 → 3</text><text class="tm-text" font-size="23" x="510" y="330" text-anchor="middle">3 → 1 → 0 → 2</text><text class="tm-text" font-size="18" x="690" y="329" text-anchor="middle" direction="rtl">معتبر</text><rect class="tm-gold" x="60" y="356" width="680" height="44" rx="10"/><text class="tm-text" font-size="23" x="260" y="386" text-anchor="middle">2 → 0 → 1 → 3</text><text class="tm-text" font-size="18" x="610" y="385" text-anchor="middle" direction="rtl">نامعتبر: کار جلوتر از پیشنیازها</text><text class="tm-text-accent" font-size="18" x="400" y="433" text-anchor="middle" direction="rtl">وابستگی تعیینکننده است، نه شمارهٔ کار</text></svg>
```
از حدس ترتیب تا کار آماده
| روش / گام | خروجی | \(\mathrm{indegree}(2)\) | کارهای آماده | نکته | هزینه |
| --- | --- | --- | --- | --- | --- |
| Brute Force | همهٔ جایگشتها | — | — | \(4!=24\) ترتیب؛ بررسی پیشنیازها | \(O(V!\,(V+E))\) |
| شروع | \([\,]\) | \(2\) | \(\{0,1,3\}\) | \(\mathrm{indegree}(0)=\mathrm{indegree}(1)=\mathrm{indegree}(3)=0\) | — |
| انجام \(0\) | \([0]\) | \(1\) | \(\{1,3\}\) | \(2\) هنوز آماده نیست | — |
| انجام \(1\) | \([0,1]\) | \(0\) | \(\{2,3\}\) | آخرین وابستگی \(2\) برطرف شد | — |
| انجام \(2\) | \([0,1,2]\) | — | \(\{3\}\) | — | — |
| انجام \(3\) | \([0,1,2,3]\) | — | \(\varnothing\) | اسکنها: \(O(V^2)\)؛ کاهشها: \(O(E)\) | \(O(V^2+E)\) |
| Kahn | \([\,]\) | \(2\) | \([0,1,3]\) | افزودن به صف فقط هنگام صفرشدن indegree | — |
پیادهسازی با صف و اجرای مثال
```python
from collections import deque
def dependencyorder(n, edges):
adj = [[] for _ in range(n)]
indegree = [0] * n
for task, pre in edges:
adj[pre].append(task)
indegree[task] += 1
queue = deque(u for u in range(n) if indegree[u] == 0)
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in adj[u]:
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
return order if len(order) == n else None
```
**اجرای مثال:** \(n=4\)، یالها: \(0\to2\)، \(1\to2\)؛ رأس \(3\) مستقل است. ابتدای صف در سمت چپ است.
| رأس برداشتهشده | `queue` | `indegree[2]` | `order` |
|---|---|---|---|
| شروع | \([0,1,3]\) | \(2\) | \([]\) |
| \(0\) | \([1,3]\) | \(1\) | \([0]\) |
| \(1\) | \([3,2]\) | \(0\) | \([0,1]\) |
| \(3\) | \([2]\) | \(0\) | \([0,1,3]\) |
| \(2\) | \([]\) | \(0\) | \([0,1,3,2]\) |
**شرط ورود به صف:** شمارنده تازه صفر شده باشد.
**یال تکراری:** هم در `adj` نگه داشته میشود و هم در `indegree` شمرده میشود.
**نتیجه:** \(\operatorname{len}(order)=4=n\)؛ خروجی \([0,1,3,2]\) است.
چرا ترتیب درست و هزینه خطی است؟
**invariant شمارنده**
شمارندهٔ هر رأس انجامنشده، تعداد یالهای ورودی از رأسهای انجامنشده است.
هر یال خروجی، یک کاهش؛ حتی یالهای تکراری.
**چرا انتخاب از صف امن است؟**
شمارندهٔ \(0\): هیچ پیشنیاز انجامنشدهای وجود ندارد.
وابستگی تازه ساخته نمیشود؛ شمارنده فقط کاهش مییابد.
هر رأس فقط یک بار آماده میشود؛ بدون visited جدا.
**صف خالی، الزاماً موفقیت نیست**
\(0\to1\to0\)
\(d(0)=d(1)=1\)، پس صف از ابتدا خالی است.
خروجی ناقص میماند.
**چرا خروجی ناقص یعنی چرخه؟**
صف خالی و رأس باقیمانده ← هر رأس باقیمانده پیشنیازی باقیمانده دارد.
دنبالکردن پیشنیازها ← تکرار رأس ← چرخه.
ترتیب کامل دقیقاً برای DAG ممکن است.
\(\mathrm{processed}<n\): وجود چرخه، نه چرخهایبودن همهٔ رأسهای باقیمانده.
**زمان خطی**
ساخت فهرستها و صف: \(O(V)\)
هر یال: یک بار ساخت، یک بار پردازش.
هر رأس: حداکثر یک ورود و یک خروج از صف.
زمان کل: \(O(V+E)\)
**حافظه، با احتساب گراف**
adj: \(O(V+E)\)
شمارندهها، صف و خروجی: هرکدام \(O(V)\)
حافظهٔ کل: \(O(V+E)\)
تستهای هدفدار برای ترتیب وابستگیها
**قرارداد خروجی و رأسهای بدون یال**
بدون یال:
\(n=0\): خروجی \([]\)، نه `None`
\(n=1\): خروجی \([0]\)
\(n=2\): هر دو خروجی \([0,1]\) و \([1,0]\) معتبرند.
صف اولیه: بررسی همهٔ رأسها، نه فقط رأسهای حاضر در `edges`.
**بخشهای جدا هم باید پردازش شوند**
یالها: \(0\to1\)، \(2\to3\)
صف: \([0,2]\)
انجام \(0\): صف \([2,1]\)
انجام \(2\): صف \([1,3]\)
خروجی کامل: \([0,2,1,3]\)
**چرخه: شکست، حتی با خروجی جزئی**
self-loop: \(0\to0\)
شمارندهٔ \(0\): \(1\)؛ صف: \([]\)؛ پاسخ: `None`
چرخه همراه با کار مستقل: کار مستقل انجام میشود، اما همهٔ رأسها پردازش نمیشوند؛ پاسخ نهایی همچنان `None` است.
**خطا: دو قرارداد ناسازگار**
دو نسخه از \(0\to1\)؛ شمارندهٔ \(1\): \(2\)
همسایههای \(0\) در `set`: فقط یک نسخه
پس از انجام \(0\): \(2\to1\)
رأس \(1\) آماده نمیشود؛ شکستِ اشتباه!
**یال تکراری: یکی از دو قرارداد**
حفظ تکرارها در فهرست و شمارنده:
انجام \(0\) ← دو بار کاهش شمارندهٔ \(1\): \(2\to1\to0\)؛ رأس \(1\) آماده است.
یا یکتا کردن یالها از ابتدا:
شمارندهٔ \(1\): \(1\to0\)؛ رأس \(1\) آماده است.
این دو قرارداد را مخلوط نکن.
**تست اعتبار، نه یک ترتیب خاص**
همهٔ رأسها دقیقاً یکبار در خروجی باشند.
برای هر یال \(u\to v\): \(\operatorname{pos}(u)<\operatorname{pos}(v)\).
تمرین از صفر: جهت یال، امنبودن شمارندهٔ صفر و دلیل چرخهبودن شکست را توضیح بده.
Back to course