ParsX.com
پذیرش پروژه از دانشجویی ... تا سازمانی 09376225339
 
   ProfileProfile   Log in to check your private messagesLog in to check your private messages  |  FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups Log inLog in   RegisterRegister 

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

 
Post new topic   Reply to topic    ParsX.com Forum Index -> اصول ساختمان داده ها
View previous topic :: View next topic  
Author Message
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 2973
Location: Tehran

PostPosted: Mon Apr 26, 2010 10:05 am    Post subject: topological sort مرتب سازی توپولوژیکی Reply with quote

فرض کنیم 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 مرتب سازی توپولوژیکی معروف است.
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 2973
Location: Tehran

PostPosted: Mon Apr 26, 2010 10:25 am    Post subject: Reply with quote

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

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

    7. پایان
Back to top
Display posts from previous:   
Post new topic   Reply to topic    ParsX.com Forum Index -> اصول ساختمان داده ها All times are GMT + 3.5 Hours
Page 1 of 1

 
Jump to:  
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