مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

این صفحه فقط خواندنی است. شما می‌توانید متن صفحه را مشاهده کنید، اما نمی‌توانید آن را تغییر دهید. اگر فکر می‌کنید که مشکلی رخ داده است، مدیر ویکی را در جریان بگذارید.

====== گراف جهت‌دار بدون دور ======
در این قسمت به بررسی الگوریتم‌های مخصوص گراف جهت‌دار بدون دور می‌پردازیم.
===== مرتب‌سازی توپولوژیکی =====
**تعریف مسأله**: یک گراف جهت‌دار داریم که رابطه‌ی بین رأسهای آن پیشنیازی است؛ یعنی اگر از یک رأس $u$ به یک رأس $v$ یال جهت دار باشد، به این معنی است که باید $u$ قبل از $v$ انجام شده باشد. به ترتیب انجام کارها با رعایت پیش‌نیاز، ترتیب توپولوژیکی می‌گویند.

مرتب‌سازی توپولوژیکی یکتا نیست و الگوریتم‌هایی که در ادامه می‌آیند یکی از مرتب‌سازی‌های توپولوژیکی را تولید می‌کنند. 
برای تولید همه‌ی ترتیب‌های توپولوژیکی می‌توان از [[الگوریتم:جستجوی_کامل|الگوریتم پس‌گرد]] استفاده کرد.

زمان اجرای الگوریتم‌های مرتب‌سازی توپولوژیکی $O(|V|+|E|)$ است.
==== الگوریتم حذف رأس ====
هر بار رأس با درجه ورودی صفر را به آخر لیست توپولوژیکی اضافه می‌کنیم و آن را از گراف حذف می‌کنیم. این کار را ادامه می‌دهیم تا تمام رأسها به لیست اضافه شوند.

==== الگوریتم پیمایشی ====
در این الگوریتم با استفاده از [[الگوریتم:پیمایش_گراف|پیمایش عمقی گراف]]، رأسهایی که به عنوان بن‌بست علامت‌گذاری می‌شوند را در انتهای ترتیب توپولوژیکی قرار می‌دهیم.

مزیت این روش این است که می‌توان تشخیص داد که گراف دور دارد یا خیر: اگر به رأسی رسیدیم که در حال دیدن بود، دور وجود دارد.
[[http://fa.wikipedia.org/wiki/%D9%85%D8%B1%D8%AA%D8%A8%E2%80%8C%D8%B3%D8%A7%D8%B2%DB%8C_%D8%AA%D9%88%D9%BE%D9%88%D9%84%D9%88%DA%98%DB%8C%DA%A9%DB%8C|مطالب بیشتر در مورد مرتب‌سازی توپولوژیکی]]
===== طولانی‌ترین مسیر =====
برای پیدا کردن طولانی‌ترین مسیر، ابتدا یک ترتیب توپولوژیکی از رأسهای گراف می‌سازیم. در آرایه‌ای طولانی‌ترین مسیر به هر رأس را نگه می‌داریم. ابتدا همه‌ی مقدارها را ۰ می‌دهیم (مسیر تک رأسی). به ترتیب توپولوژیکی رأس‌ها را می‌بینیم و یالهای ورودی به آن رأس را در نظر می‌گیریم: اگر جمع طول آن یال و طولانی‌ترین مسیر به رأس سر دیگر یال از جواب فعلی بیشتر بود، آن را جایگزین می‌کنیم. چون ترتیب توپولوژیکی است، مسیرها رأس تکراری ندارند.

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

[[http://en.wikipedia.org/wiki/Longest_path_problem|مطالب بیشتر در مورد طولانی‌ترین مسیر]]

مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

ابزار کاربر

ابزار سایت

ابزار صفحه