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. پایان