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

[Y@SiN]

فرض کنیم S یک گراف جهت دار باشد.

1. هر گره این گراف نمایانگر یک کار می باشد.
2. هر یال این گراف که به شکل (u,v) نمایش داده می شود بیانگر این است که کار u قبل از کارv انجام می شود.


مثلا اگر در این گراف یک دور داشته باشیم که مسیر زیر را طی کرده باشد به این صورت نمایش می دهیم : (u,v,w,u)
این مسیر این مطلب را بیان می کند که وظیفه v قبل از اتمام وظیفه u نمی تواند شروع شود . وظیفه w نیز قبل از اتمام وظیفه v نمی تواند شروع شود و در آخر به این مطلب می رسیم که وظیفه u نمی تواند قبل از اتمام وظیفه w انجام شود . از این تناقض به یک نتیجه می رسیم و آن اینکه در این نوع گراف ها که اتمام یک وظیفه و وابستگی آنها بیان می شود نمی توان دور داشت .
به این دست گراف ها گراف های acyclic یا cycle-free می گویند.
خانواده این گراف ها به گراف های جهت دار بدون دور یا Directed Acyclic Graph (DAG) معروف هستند .
اصلی ترین فعالیتی که روی یک dag انجام می شود پردازش گره ها یکی بعد از دیگری است . این مرتب سازی خطی که منحصر بفرد نیز نمی باشد به topological sort مرتب سازی توپولوژیکی معروف است.

[Y@SiN]

لم 1. اگر گراف dag محدودی داشته باشیم آنگاه حداقل یک مرتب سازی توپولوژیکی نیز می توانیم داشته باشیم.
الگوریتم:
در مرحله اول باید از یک گره که درجه ورودی صفر دارد شروع کرد.
به کمک (تابع یا آرایه) INDEG درجه ورودی گراف ها را پیدا می کنیم.

1. تمام گره های با درجه ورودی صفر را پیدا کن و در صف قرار بده.
2. مراحل زیر را تا زمانی که صف خالی نشده است ادامه بده:

3.گره را از جلوی صف پاک کن ( N )
4. برای گره های مجاور(M) گره مذکور عملیات زیر را انجام بده :



5. INDEG(M)--;
6. اگر INDEG(M) صفر شد آن را به انتهای صف اضافه کن.


7. پایان