ترتیب توپولوژیک و اجزای قویاً همبند
ترتیب توپولوژیک DAG با الگوریتم Kahn: ترتیب انجام کارها با وابستگی + تشخیص دور + کاربردها
مسئله ترتیب کارها
کارهایی با وابستگی: «A قبل از B». چه ترتیبی معتبر است؟ این ترتیب توپولوژیک گراف جهت‌دار بی‌دور (DAG) است!
کاربردها: ترتیب دروس دانشگاه، build system (make)، pip/npm (وابستگی پکیج‌ها)، زمان‌بندی پروژه.
الگوریتم Kahn (BFS-based)
- درجه ورودی هر رأس را حساب کن
- صف = رئوس با درجه ۰ (بدون پیش‌نیاز)
- بردار از صف، به ترتیب اضافه کن؛ درجه همسایه‌ها را کم کن
- همسایه با درجه ۰ ← صف
اگر همه رئوس پردازش نشدند ← دور وجود دارد (ترتیب ممکن نیست)!
مثال
دروس: ریاضی۱ → فیزیک → ریاضی۲ → هوش مصنوعی
ریاضی۱ → برنامه‌نویسی → هوش مصنوعی
درجه ۰: [ریاضی۱]
پردازش: ریاضی۱ → فیزیک(۰!)، برنامه‌نویسی(۰!)
پردازش: فیزیک، برنامه‌نویسی → ریاضی۲(۰!)
پردازش: ریاضی۲ → هوش مصنوعی(۰!)
ترتیب: ریاضی۱، فیزیک، برنامه‌نویسی، ریاضی۲، هوش مصنوعی ✓ویژگی‌ها
- ترتیب توپولوژیک یکتا نیست — چند ترتیب معتبر ممکن
- فقط برای DAG (بی‌دور) — Kahn دور را هم تشخیص می‌دهد!
- O(V + E) — هر رأس و یال یک‌بار
اجزای قویاً همبند (SCC) — اشاره
در گراف جهت‌دار، زیرگرافی که هر دو رأس به هم مسیر دارند. الگوریتم‌های Kosaraju/Tarjan با DFS دوگانه SCC ها را در O(V+E) می‌یابند — پایه تحلیل شبکه‌های اجتماعی و فشرده‌سازی گراف. جزئیات کامل، منابع پیشرفته‌تر.
نکته مصاحبه: «ترتیب با وابستگی» = پرچم توپولوژیک! و اگر پرسیدند «آیا ممکن است؟» — Kahn اجرا کنید؛ اگر گیر کرد، دور هست و ترتیب وجود ندارد.
جمع‌بندی
- توپولوژیک: ترتیب رئوس DAG با احترام به جهت یال‌ها
- Kahn: درجه ورودی + صف — ساده و کارآمد
- پردازش ناقص = دور = ترتیب ناممکن
- کاربرد: دروس، build، وابستگی پکیج
این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.