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

[farnaz330]

سلام
در این نوع مرتب سازی (تپولوژی)ورودی یک گراف جهت دار است که دور ندارد فرض کنید هر راس دارای مقداری باشد و یالها از مقایسه مقدار راسها ایجاد و دارای جهت میشوند برای اینکه بتوانیم از الگوریتم مرتب سازی تپولوژی استفاده کنیم چندتا از این مقایسه ها باید انجام دهیم یا چندتا یال جهتدار باید پیدا کنیم و چه اگوریتمی برای پیدا کردن یالها وجود دارد؟
لطفا من را راهنمایی کنید

[whitehat]

من سوال شما را درست متوجه نشدم!؟ این چیزی که نوشتید صورت مسئله مرتب سازی توپولوژیکی هست.
برای اجرای این الگوریتم شما به یک زمان خطی برابر تعدا نودها + تعداد یالها نیاز دارید.
برای اجرای الگوریتم اگر صف Q را داشته باشیم و لیست مرتب شده برابر L باشد الگوریتم را بصورت زیر می توان نوشت:
1- لیست L را خالی کنید
2- تمام نودهایی که یال ورودی ندارند را در صف Insert کنید
3- تا هنگامی که صف خالی نشده مراحل زیر را انجام دهید
3-1 نود n را از صف Remove کنید
3-2 نود n را به لیست L اضافه کنید
3-3 به ازای هر نود m با یال e که از n به m است مراحل زیر انجام شود
3-3-1 از گراف یال e را حذف کنید
3-3-2 اگر نود e یال دیگری ندارد آنرا به صف اضافه کنید
4- اگر گراف یال داشت خطا روی داده چون گراف نباید دارای دور باشد
5- والا لیست L را چاپ کن

اگر سوالی دیگری دارید بپرسید ، یا اگه لازم هست مثال بزنم
موفق باشید

[farnaz330]

از پاسخی که دادین متشکرم ولی سوال من مربوط به شرایط این مرتب سازی است برای مثال فرض کنید راسهای زیر را با این مقدارها داریم:

1:1
2:6
3:5
4:7

و یالهای زیر نیز داده شده باشد
2-->1و3-->1که به معنی این است که مقدار راس2از مقدار راس1 بزرگتر است با این اطلاعات این الگوریتم نتیجه زیر را خواهد داد که با توجه به مقدار راسها درست نیست
1423 پس نیاز به یکسری مقایسه بین مقدار راسها داریم تا مرتب سازی انجام شود سوال من در مورد این مقایسهاست.لطفا باز هم من را راهنمایی کنید

[saeed_javanmardi]

سلام دوستان من 2 تا سورس کد عالی برای شما در سایت گذاشته ام که می توانید دانلود کنید
یکی با عنوان topolo.rar که تضمینی درست کار می کند و دیگری که مطمئن نیستم درست کار میکند ولی احتمالا درست کار می کنه با عنوان topological_sort
از 2 تا الگوریتم متفاوت استفاده شده است
در ضمن از برنامه نویسی 2 لایه استفاده کرده ام
سعید جوانمردی