مرتب سازی توپولوژیکی در جاوا (Topological Sort)

در این جلسه تیم کدگیت را با آموزش مرتب سازی توپولوژیکی در جاوا همراهی کنید. پیش نیاز این آموزش شامل موارد زیر است:

  1. جست و جوی اول عمق در جاوا
  2. رابط برنامه‌نویسی گراف جهت دار
  3. صف در جاوا
  4. پشته در جاوا
  5. شی گرایی در جاوا
  6. Constructor در جاوا
  7. حلقه for در جاوا
  8. دستور if در جاوا
  9. مدیریت استثناها
  10. آشنایی با روش بازگشتی

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

در نظریه گرافها، یک مرتب‌سازی موضعی یا ترتیب موضعی یک گراف بدون دور جهت دار، یک ترتیب خطی از همه رئوس آن است به طوری که هر گره قبل از همه گره‌هایی می‌آید که از آن به آنها یال خارج شده است. هر درخت بدون دور جهت دار یک یا چند مرتب‌سازی موضعی دارد. اگر گراف بدون دور نباشد آنگاه هیچ ترتیب خطی به این صورت وجود ندارد (ویکیپدیا).

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

برای مرتب‌سازی گراف، روی گراف پیمایش عمق‌اول می‌زنیم به هر راسی که رسیدیم آنرا علامت می‌زنیم.

هنگام خروج از آن راس یک علامت دیگر به معنی پایان بررسی آن راس روی آن می‌زنیم و آنرا در پشته‌‌ای می‌ریزیم که جواب مسئله یعنی رئوس مرتب شده است. حال اگر به راسی رسیدیم که علامت وارد شدن به آن بود ولی علامت پایان نداشت یعنی که در گراف دور وجود دارد و مرتب‌سازی ممکن نیست.

سپس روی بقیه رئوسی که علامت نخورده‌اند پیمایش انجام می‌دهیم ولی وارد راس‌هایی که علامت دارند نمی‌شویم(opedia.ir).

کد الگوریتم مرتب سازی توپولوژیکی در جاوا

برای پیاده سازی این مرتب سازی، ما از پشته و صف نیز استفاده کردیم ولی در اینجا به توضیح آنها نمی‌پردازیم. کلاس‌های به کار رفته در این پیاده سازی به صورت زیر است:

  1. Bag
  2. Stack
  3. Queue
  4. Node
  5. Digraph
  6. ListIterator
  7. DepthFirstOrder
  8. DirectedCycle
  9. Topological

در لیست بالا ما شماره‌های 1 تا 6 را در آموزش‌های قبلی توضیح داده‌ایم و در این آموزش سه کلاس DepthFirstOrder و DirectedCycle و Topological را بررسی می‌کنیم.

DirectedCycle

کار این کلاس پیدا کردن دور در گراف است و این کار را با پیمایش اول عمق انجام می‌دهد. کد این کلاس به صورت زیر می‌باشد:

این کلاس شامل متدهای زیر می‌باشد:

  1. Dfs: متد پیمایش اول عمق می‌باشد.
  2. HasCycle: در صورت دور در گراف متد true برمی‌گرداند.
  3. Cycle: لیست نودهایی که در گراف دور تشکیل داده‌اند را برمی‌گرداند.
  4. DirectedCycle: این متد Constructor ما است و در ورودی یک گراف جهت دار را می‌گیرد.

همچنین در کد بالا از فیلدهای زیر استفاده شده است:

  1. Marked: در صورت ملاقات یک راس مقدار آن true می‌شود(Marked[v]).
  2. EdgeTo: راس‌های قبلی در مسیر رسیدن به راس V را نگه‌داری می‌کند.
  3. Cycle: راس‌هایی که در گراف، دور تشکیل داده‌اند.
  4. OnStack: راس‌هایی که در پشته هستند.

DepthFirstOrder

این کلاس مرتب سازی توپولوژیکی را برای ما انجام می‌دهد.کد این کلاس به صورت زیر است:

کد بالا شامل متدهای زیر می‌باشد:

  1. ReversePost: این متد راسهای مرتب شده را برمی‌گرداند.
  2. Dfs: متد پیمایش اول عمق
  3. DepthFirstOrder: این متد Constructor است و یک گراف جهت دار را به عنوان ورودی می‌گیرد.

همچنین کلاس بالا شامل فیلدهای زیر می‌باشد:

  1. Marked: در صورت ملاقات یک راس مقدار آن true می‌شود(Marked[v]).
  2. Pre: محل قرار گیری راس V در لیست PreOrder
  3. Post: محل قرار گیری راس V در لیست PostOrder
  4. PreCounter: تعداد راسها در PreOrder
  5. PostCounter: تعداد راسها در PostOrder
  6. PreOrder: لیست راسها در دنباله PreOrder
  7. PostOrder: لیست راسها در دنباله PostOrder

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

برای تست کدهای بالا، کلاس Topological را به صورت زیر بنویسید:

در کد بالا دو فیلد order و rank استفاده شده است که به ترتیب لیست راس های ما در مرتب سازی و محل قرار گیری راس ها در مرتب سازی است. یک Constructor هم نوشتیم که یک گراف جهت دار را میگیرد با استفاده از کلاس DirectedCycle بررسی میکند گراف دور دارد یا خیر! پس از بررسی با استفاده از کلاس DepthFirstOrder لیست مرتب سازی توپولوژیکی ما را دریافت و چاپ میکند. در Main نیز کلاس Topological را صدا زدیم.

پسورد: www.codegate.ir

 

دسته : java, جاوا, گراف در جاوا, مرتب سازی در جاوا

دیدگاه بگذارید

نظر شما چیست؟

مطلع کردن شما از
avatar

wpDiscuz