مولفه‌های قویاً همبند، روش کوساراجو
برای یافتن مولفه‌های قویاً همبند یک در یک گراف جهت دار، روش‌های مختلفی وجود دارد. یکی از بهترین الگوریتم‌ها از نظر سرعت اجرا، الگوریتم کوساراجو است که در سال 1978 توسط Sambasiva Rao Kosaraju دانشمند هندی علوم کامپیوتر ارائه شد. این الگوریتم در ابتدا مانند روشی که در مرتب‌سازی موضعی گراف با استفاده از پیمایش اول‌عمق انجام دادیم، پشته‌ای از رئوس را تشکیل می‌دهد. سپس به ترتیب رئوس داخل پشته مجددا پیمایش اول‌عمق را بر روی گراف معکوس انجام می‌دهد.
این مطلب نیازمند آشنایی با مفاهیم و اصطلاحات بسیاری در مبحث
نظریه‌ی گراف
می‌باشد. پیشنهاد می‌شود قبل از ادامه، مطالب زیر را به ترتیب مطالعه نمایید:
- گراف جهت‌دار
- گراف معکوس
- گراف قویا همبند
- مولفه‌های قویاً همبند گراف
- پیمایش اول‌عمق گراف (DFS)
- مرتب‌سازی موضعی رئوس گراف (Topological Sorting)
تگ ها
- پیشنهادی
- تازهها
- ویژهنامه
