مرتب‌سازیِ توپولوژیک ترتیبی از گره‌هایِ گرافِ جهت‌دار می‌دهد که هر پیش‌نیاز پیش از وابسته‌اش بیاید. چنین ترتیبی برایِ گرافِ بدونِ چرخهٔ جهت‌دار وجود دارد و الزاماً یکتا نیست. این راهنما با الگوریتمِ Kahn، تعدادِ وابستگیِ باقی‌مانده و صفِ کارهایِ آماده را واقعاً به‌روز می‌کند؛ هیچ کارِ واقعی یا انتشارِ سایتی اجرا نمی‌شود.
جهتِ یال را اول توافق کنیم
در قراردادِ این صفحه، u→vیعنی uپیش‌نیازِvاست. شش گرهِA،B،C،D،EوUداریم. یال‌ها A→C، B→C، C→DوB→Eهستند. Uمنزوی است؛ نبودِ یال به معنیِ حذفِ آن از مجموعهٔ کارها نیست. این شناسه‌ها فقط یک دفترِ آموزشی‌اند و وضعیتِ واقعیِ پروژه یا مشتری را نشان نمی‌دهند.
اگر در فایلِ دیگری یال برعکس و به معنیِ «وابسته→پیش‌نیاز» ثبت شده باشد، همین الگوریتم رویِ آن قرارداد، ترتیبِ دیگری می‌دهد. نامِ گراف یا ابزار جهت را معلوم نمی‌کند. پیش از مرتب‌سازی، معنایِ رابطه را همراهِ داده ثبت کنید و تمامِ گره‌ها، حتی بی‌یال‌ها را نگه دارید.
indegree چه چیزی را می‌شمارد؟
درجهٔ ورودی تعدادِ یال‌هایِ واردشونده به گره است. در آغاز، A=۰، B=۰، C=۲، D=۱، E=۱وU=۰است. گره‌هایی که درجهٔ ورودیِ باقی‌مانده‌شان صفر است آماده‌اند، چون پیش‌نیازی در بخشِ باقی‌مانده ندارند. فهرستِ آغازینِ آماده‌ها A،BوUاست.
هر بار یک گرهٔ آماده را برمی‌داریم، در خروجی می‌گذاریم و درجهٔ ورودیِ هر وابسته‌اش را یک واحد کم می‌کنیم. اگر درجهٔ یک وابسته به صفر رسید، به آماده‌ها اضافه می‌شود. دادهٔ اصلیِ گراف در این فایل تغییر نمی‌کند؛ دفترِ indegree جداست. برایِ تساویِ چند آماده، ترتیبِ واژگانیِ صعودی را سیاستِ اجرایِ اول قرار داده‌ایم.
مرحله‌هایِ واقعیِ همین گراف
| انتخاب | اصلاحِ درجه | چه چیزی آماده می‌شود؟ |
|---|---|---|
| A | Cاز۲به۱ | Cهنوز آماده نیست |
| B | Cاز۱به۰ وEاز۱به۰ | CوE |
| C | Dاز۱به۰ | D |
| D | یالِ خروجی ندارد | موردِ تازه ندارد |
| E | یالِ خروجی ندارد | موردِ تازه ندارد |
| U | گرهِ جدا | در خروجی حفظ می‌شود |
ترتیبِ اول A،B،C،D،E،Uاست. کنترلِ مستقل، جایگاهِ دو سرِ تک‌تکِ یال‌ها را می‌سنجد؛ مثلاً جایگاهِBباید هم ازC و هم ازEکمتر باشد. صرفِ هم‌اندازه‌بودنِ فهرستِ خروجی با تعدادِ گره‌ها برایِ درستیِ ترتیب کافی نیست.
ترتیبِ دیگری هم می‌تواند درست باشد
این بار از میانِ آماده‌ها، بزرگ‌ترینِ شناسهٔ واژگانی را برمی‌داریم. خروجی U،B،E،A،C،Dمی‌شود و باز هم تمامِ پیش‌نیازها جلوترند. AوBدر داده رابطه‌ای با یکدیگر ندارند؛ جلو یا عقب آمدنشان تا وقتی یال‌ها رعایت شوند مجاز است. الگوریتم بهینه‌ترینِ زمان‌بندیِ منابع را از همین رابطهٔ پیش‌نیازی نتیجه نمی‌دهد.
اگر مدت، ظرفیتِ اجرا، مهلت یا اولویتِ تجاری هم مطرح باشد، مسئلهٔ زمان‌بندی اطلاعاتِ بیشتری می‌خواهد. دو ترتیبِ معتبر از نظرِ وابستگی لزوماً زمانِ پایانِ برابر ندارند؛ این تمرین اصلاً مدت و منابع تعریف نکرده است. عددِ جایگاه را زمانِ واقعیِ شروع ننامید.
یک چرخه، یک خروجیِ ناقص
اکنون فقط یالِD→Bرا اضافه می‌کنیم. چرخهٔB→C→D→Bشکل می‌گیرد. الگوریتم باAوUپیش می‌رود، اما بعد آماده‌ای باقی نمی‌ماند وگره‌هایِB،C،D،Eمسدود می‌مانند. خروجیِ[A،U] ترتیبِ کاملِ توپولوژیک نیست؛ فایل، completeرا falseثبت می‌کند و باقی‌مانده را جدا نشان می‌دهد.
نکتهٔ مهم این است که Eعضوِ چرخه نیست؛ فقط بهBوابسته است که درچرخه گیر کرده. همهٔ باقی‌مانده را «گره‌هایِ چرخه» ننامید. کدِ کمکیِ مستقل بررسی می‌کند از هر گره آیا مسیری با دست‌کم یک یال به خودش برمی‌گردد؛ فقطB،CوDاین ویژگی را دارند. این بررسیِ جدا، خروجیِ مستقیمِ Kahnنیست.
حدودِ ورودی و تفاوت با پیمایش
فایلْ گرافِ جهت‌دارِ ساده با تمامِ مقصدهایِ اعلام‌شده می‌خواهد؛ یالِ تکراری و مقصدِ ثبت‌نشده را نمی‌پذیرد. درگرافِ اصلی هنگامِ اجرا تغییری نمی‌دهیم. مرتب‌سازیِ فهرستِ آماده‌ها در هر گام انتخابِ روشنِ آموزشیِ ماست، نه ادعایِ سریع‌ترینِ پیاده‌سازی. NetworkXاجرا نشده و زمان یا حافظه بنچمارک نشده است.
BFS وDFS ترتیبِ کشفِ مسیر از مبدأ را می‌سازند؛ اینجا تمامِ پیش‌نیازها باید رعایت شوند وحتی گرهِ منزوی در خروجی باشد. گرافِ دانش هم معنا و هویتِ رابطه را بررسی می‌کند؛ ترتیبِ درست، صحتِ تعریفِ پیش‌نیاز را اثبات نمی‌کند. برایِ نیازِ پاسخ‌گویی و پیگیری، کارِ مجاز و خروجیِ موردِ انتظار را در راهکارهایِ اپرا روشن کنید؛ این آموزش تغییری در محیطِ واقعی نمی‌دهد.
فایل تمرین و منبع
صفِ آماده‌ها، indegree و دو ترتیبِ معتبر؛ Python · دفترِ وابستگی، چرخه و گرهِ مسدودِ خارج از چرخه
- NetworkX؛ تعریفِ ترتیبِ غیر‌یکتا و ناممکن‌بودنِ ترتیبِ کامل در چرخه
- منبعِ اصلی؛ بخشِ indegree و گره‌هایِ صفر و باقی‌ماندهٔ چرخه‌دار خوانده شد؛ پیاده‌سازیِ آموزشیِ صف با کتابخانه یکی نیست
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.