مرتب‌سازی توپولوژیک

کاهش و حل

گره‌های گراف جهت‌دار بی‌دور را طوری می‌چیند که هر یال از گره‌ی قبلی به بعدی برود؛ مثل ترتیب گذراندن درس‌ها با پیش‌نیاز.

در گراف جهت‌دار بی‌دور (DAG)، ترتیب توپولوژیک چیدن گره‌ها در یک صف است، طوری که هر یال u → v از چپ به راست برود. مثال کلاسیک: درس‌ها و پیش‌نیازهایشان.

ادامه‌ی توضیح ↓

زمان: O(V + E)
حافظه: O(V)
CLRS، بخش ۲۰.۴
هوروویتز–ساهنی، فصل ۶
گریمالدی، فصل ۷

ورودی:

V=7 · E=8 · src=Aخروجی PDF

هفت درس؛ یال X → Y یعنی X پیش‌نیاز Y است.

from collections import deque
def topological_sort(graph, src):
indegree = {v: 0 for v in graph}
for u in graph:
for v, _ in graph[u]:
indegree[v] = indegree[v] + 1
queue = deque(v for v in graph if indegree[v] == 0)
order = []
while queue:
u = queue.popleft()
order.append(u)
for v, _ in graph[u]:
indegree[v] = indegree[v] - 1
if indegree[v] == 0:
queue.append(v)
if len(order) < len(graph):
return None
return order

ناوردا: indegree[v] تعداد یال‌های ورودی v از گره‌هایی است که هنوز در order نیامده‌اند.

شروع اجرا

گره‌ی جاری (u)
درخت کوتاه‌ترین مسیر تا اینجا
یالِ در حال بررسی

صف `queue`

خالی

متغیرهای محلی

src'A'

نارنجی = در همین گام عوض شد

graph dict

'A': [('C', 1)]
'B': [('C', 1), ('D', 1)]
'C': [('E', 1)]
'D': [('E', 1), ('F', 1)]
'E': [('G', 1)]
'F': [('G', 1)]
'G': []

Call stack

topological_sort()خط 4

گام ۱ از ۹۵

رشد تعداد عملیات با اندازه‌ی ورودی

میانگین ۵ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.

remove_edge
take
ورودی فعلی (n=7)

نمایش به شکل جدول

n	remove_edge	take
4	5.2	4
8	13.8	8
12	20.8	12
16	28	16
20	35.4	20
24	37.2	24
28	47.2	28

توضیح

ایده

الگوریتم کان

برای هر گره تعداد یال‌های ورودی‌اش (indegree) را بشمار.
گره‌هایی که یال ورودی ندارند آماده‌اند؛ آن‌ها را در صف بگذار.
یک گره‌ی آماده بردار، به ترتیب اضافه کن و یال‌های خروجی‌اش را «حذف» کن (indegree همسایه‌ها یکی کم می‌شود). هر همسایه‌ای که indegreeش صفر شد، آماده است.

اگر در پایان گره‌ای جا ماند، آن گره روی یک دور است و ترتیب توپولوژیک وجود ندارد.

هزینه

هر گره یک بار وارد صف می‌شود و هر یال یک بار حذف می‌شود: O(V + E).

در trace به چه چیزی نگاه کنی

عدد کنار هر گره indegree آن است؛ وقتی صفر شد، گره وارد صف می‌شود.
در ورودی «دور» ببین سه گره‌ی دور هیچ‌وقت به صفر نمی‌رسند.