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

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

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

زمان اجرای الگوریتم‌های مرتب‌سازی توپولوژیکی $O(|V|+|E|)$ است.

هر بار رأس با درجه ورودی صفر را به آخر لیست توپولوژیکی اضافه می‌کنیم و آن را از گراف حذف می‌کنیم. این کار را ادامه می‌دهیم تا تمام رأسها به لیست اضافه شوند.

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

مزیت این روش این است که می‌توان تشخیص داد که گراف دور دارد یا خیر: اگر به رأسی رسیدیم که در حال دیدن بود، دور وجود دارد. مطالب بیشتر در مورد مرتب‌سازی توپولوژیکی

برای پیدا کردن طولانی‌ترین مسیر، ابتدا یک ترتیب توپولوژیکی از رأسهای گراف می‌سازیم. در آرایه‌ای طولانی‌ترین مسیر به هر رأس را نگه می‌داریم. ابتدا همه‌ی مقدارها را ۰ می‌دهیم (مسیر تک رأسی). به ترتیب توپولوژیکی رأس‌ها را می‌بینیم و یالهای ورودی به آن رأس را در نظر می‌گیریم: اگر جمع طول آن یال و طولانی‌ترین مسیر به رأس سر دیگر یال از جواب فعلی بیشتر بود، آن را جایگزین می‌کنیم. چون ترتیب توپولوژیکی است، مسیرها رأس تکراری ندارند.

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

مطالب بیشتر در مورد طولانی‌ترین مسیر