Posted: Mon Apr 26, 2010 10:05 am Post subject: topological sort مرتب سازی توپولوژیکی
فرض کنیم 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 مرتب سازی توپولوژیکی معروف است.
لم 1. اگر گراف dag محدودی داشته باشیم آنگاه حداقل یک مرتب سازی توپولوژیکی نیز می توانیم داشته باشیم.
الگوریتم:
در مرحله اول باید از یک گره که درجه ورودی صفر دارد شروع کرد.
به کمک (تابع یا آرایه) INDEG درجه ورودی گراف ها را پیدا می کنیم.
1. تمام گره های با درجه ورودی صفر را پیدا کن و در صف قرار بده.
2. مراحل زیر را تا زمانی که صف خالی نشده است ادامه بده:
3.گره را از جلوی صف پاک کن ( N )
4. برای گره های مجاور(M) گره مذکور عملیات زیر را انجام بده :
5. INDEG(M)--;
6. اگر INDEG(M) صفر شد آن را به انتهای صف اضافه کن.
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum
Profile 
Log in to check your private messages | 
FAQ 
Search 
Memberlist 
Usergroups 
Log in
Register
