مولفه‌های قویاً همبند — Kosaraju
Strongly Connected Components — KosarajuKosaraju مولفه‌های قویاً همبند گراف جهت‌دار را با دو مرحله DFS و گراف transpose پیدا می‌کند.
اول این مفهوم را در ذهن نگه دار
Kosaraju مولفه‌های قویاً همبند گراف جهت‌دار را با دو مرحله DFS و گراف transpose پیدا می‌کند.
چطور کار می‌کند؟ ساده و مرحله‌ای
DFS اول Nodeها را بر اساس finishing time مرتب می‌کند.
سپس جهت همه edgeها برعکس می‌شود و DFSها با ترتیب finish نزولی اجرا می‌شوند؛ هر traversal یک SCC می‌سازد.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
مشخص کن گراف directed/undirected و weighted/unweighted است.
representation گراف را انتخاب کن.
state الگوریتم و حالت disconnected/cycle را صریح مدیریت کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای مولفه‌های قویاً همبند — Kosaraju هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
Varies by implementation / input constraints
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- فقط وقتی assumptionهای الگوریتم با مسئله گراف هماهنگ است از آن استفاده کن.
کجا معمولاً اشتباه می‌کنیم؟
- فراموش کردن componentهای disconnected.
- قاطی کردن shortest path وزن‌دار و بدون وزن.
- مدیریت نکردن revisit/cycle.
مدل یک پاسخ حرفه‌ای
شهود مهم این است که transpose اتصال داخل SCC را حفظ می‌کند ولی جهت ارتباط بین SCCها را برعکس می‌کند؛ همین دلیل موفقیت دو pass است.
مولفه‌های قویاً همبند — Kosaraju چه مسئله‌ای را حل می‌کند؟
Kosaraju مولفه‌های قویاً همبند گراف جهت‌دار را با دو مرحله DFS و گراف transpose پیدا می‌کند.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا Varies by implementation / input constraints است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
فراموش کردن componentهای disconnected.