موضوع مقاله: الگوریتم کساراجو | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم کساراجو | مقدمه: الگوریتم کساراجو الگوریتمی است که به منظور پیدا کردن مولفه‌های قویا همبند در یک گراف جهت‌دار استفاده می‌شود. | ## بخش 1: الگوریتم کساراجو | کساراجو این الگوریتم را با استفاده از این نکته که مؤلفه‌های قویا همبند در یک گراف جهت‌دار با مؤلفه‌های قویا همبند در معکوس آن گراف جهت‌دار برابر هستند، ارائه کرد. الگوریتم دیگری که بر پایه همین الگوریتم است، الگوریتم تارجان است که در واقع نسخهٔ بهبودیافته الگوریتم کساراجو است. در حدود ۲۰ سال بعد یعنی در سال ۱۹۹۶ نسخهٔ بهبودیافتهٔ دیگری از این الگوریتم، توسط هارولد گابو منتشر شد. مفاهیم گراف قویا همبند به گرافی گویند که هر جفت راس آن از یکدیگر قابل دسترس باشد. پیمایش این گراف را از یک راس دلخواه به وسیلهٔ یکی از الگوریتم‌های پیمایش گراف یعنی جستجوی عمق اول انجام می‌دهیم. وقتی الگوریتم جستجوی عمق اول کار خود را با یک راس به اتمام رساند، آن را در داخل پشته قرار می‌دهیم. تمام رأس‌های ملاقات شده را از پشته خارج و همین الگوریتم را بر روی راسی که در بالای پشته قرار دارد، تکرار می‌کنیم، تا زمانی که پشته خالی شود. ابتدا گراف مورد نظر را با استفاده از الگوریتم جستجوی عمق اول با شروع از راس A پیمایش می‌کنیم. مطابق آن‌چه در توضیح الگوریتم گفتیم بعد از اجرای جستجوی عمق اول بر روی گراف از راس A، راس H وارد پشته می‌شود. سپس جستجوی عمق اول بار دیگر از A ادامه پیدا کرده و در انتها، پشته به صورت زیر پر می‌شود: سر پشته --> [H, G, C, E, F, D, B, A] پس از آن معکوس گراف را محاسبه می‌کنیم. معکوس گراف مورد نظر مطابق شکل زیر است: حال مطابق آنچه در توضیح الگوریتم گفته شد، جستجوی عمق اول را بر روی گراف معکوس، با شروع از راسی که در سر پشته است (یعنی A)، اجرا می‌کنیم. | ## بخش 2: الگوریتم کساراجو | با پیمایش گراف از راس A، تنها دو راس B و D ملاقات می‌شوند؛ بنابراین ۳ راس A و B و D، تشکیل یک مؤلفهٔ قویا همبند می‌دهند. پس کافی است این ۳ راس را mark کرده (از پشته و گراف خارج کنیم) و الگوریتم را ادامه دهیم. پس الگوریتم جستجوی عمق اول را بر روی آن اجرا می‌کنیم و F و E را به عنوان یک مؤلفهٔ قویا همبند دیگر، گزارش می‌کنیم. با ادامه الگوریتم H و G و C نیز که در پشته باقی‌مانده‌اند، به عنوان آخرین مؤلفهٔ قویا همبند گزارش می‌کنیم. اثبات درستی الگوریتم در نگاهی عمیق‌تر به الگوریتم، می‌توان متوجه شد که هر چه یک راس در قسمت بالاتری از پشته قرار گیرد، به این معناست که در زمان دیرتری مراحل الگوریتم بر روی آن به پایان رسیده‌است. به بیان دیگر اگر (f(u زمان به پایان رسیدن مراحل جستجوی عمق اول بر روی راس u نظر گرفته شود، هر چه راس u در پشته بالاتر (به سر پشته نزدیک‌تر) باشد، دارای (f(u بزرگتری نیز است. (پشته در الگوریتم کساراجو نقش ترتیب نزولی (f(uها به ازای تمامی رأس‌ها است) معکوس گراف G، یعنی GT را محاسبه می‌کند. الگوریتم جستجوی عمق اول را بر روی GT اجرا می‌کند ولی رأس‌ها را با اولویت (f(u با ترتیب نزولی در نظر می‌گیرد (همان ترتیب رأس‌ها در پشته) رأس‌ها را در هر درخت حاصل از جستجوی عمق اول به عنوان یک مؤلفه قویا همبند (SCC) چاپ می‌کند. اثبات: دو حالت وجود دارد: ابتدا C1 توسط الگوریتم جستجوی عمق اول ملاقات شود: در ابتدا تمامی رأس‌های موجود در C1 ملاقات شده و سپس از طریق یال u به v، رأس‌های C2 ملاقات می‌شوند. چون C2 یالی به خارج از خود ندارد پس در ابتدا رأس‌های آن به پایان می‌رسد و سپس رأس‌های C1 به پایان می‌رسد. ابتدا C2 توسط الگوریتم جستجوی عمق اول ملاقات شود در ابتدا تمامی رأس‌های موجود در C2 ملاقات شده و چون C2 یالی به خارج از خود ندارد پس الگوریتم در همان مؤلفه به پایان می‌رسد. | ## بخش 3: الگوریتم کساراجو | بنابراین چون این الگوریتم در ابتدا (f(uها را محاسبه می‌کند و سپس در GT، الگوریتم جستجوی عمق اول را از راسی که بیشینه (f(u را در گراف G دارد، اجرا می‌کند، این راس یعنی u مطابق نتیجه‌ای که در بالا گرفته شد، دارای کمینه (f(u است. به این ترتیب، اگر مؤلفه‌ای که u در آن وجود دارد را C3 بنامیم، الگوریتم جستجوی عمق اول در ابتدا تمامی همسایگان u را در C3 ملاقات می‌کند. چون در غیر این صورت باید از C3 به یکی دیگر از مؤلفه‌ها مانند Ci یال وجود داشته باشد. چون اگر یالی از یک راس در C3 به یک راس در مؤلفه دیگر مانند Ci وجود داشت، طبق لم بالا، (f(C3 از (f(Ci بزرگتر بود که این با کمینه بودن (f(C3 تناقض است؛ بنابراین الگوریتم به درستی اولین مؤلفه قویا همبند را مشخص کرد. در مرحله بعد (f(Ci به گونه‌ای انتخاب می‌شود که در گراف G، از (f(C مربوط به تمامی مؤلفه‌ها به جز (f(C3 بزرگتر است. تحلیل زمانی همان‌طور که در توضیح الگوریتم گفته شد، الگوریتم شامل ۳ مرحله است: پیمایش گراف و پر کردن پشته معکوس کردن گراف پیمایش گراف با توجه به اولویت رأس‌ها با استفاده از پشته در صورتی که گراف به وسیله ماتریس مجاورت پیاده‌سازی شود، زمان اجرای این الگوریتم از (۲|O(|V خواهد بود. از طرف دیگر می‌دانیم اگر گراف به وسیله لیست مجاورت پیاده‌سازی شود، الگوریتم جستجوی عمق اول به زمان (|O(|V|+|E نیاز دارد که در آن V تعداد راسها و E تعداد یال هاست. برای معکوس کردن گراف نیز کافی است یک بار گراف را به وسیله جستجوی اول عمق پیمایش کرده و در گذر از هر یال جهت آن یال را عوض کنیم. می‌توان مرحله اول و مرحله معکوس کردن را در یک بار پیمایش گراف انجام دهیم به این ترتیب تنها به دو جستجوی اول عمق نیاز داریم پس در کل زمان اجرا برابر(|O(|V|+|E است. با بدست آوردن گراف مؤلفه‌های قویا همبند، بسیاری از مسایل نظریه گراف به راحتی قابل حل است. مانند: به دست آوردن راس برشی به دست آوردن یال برشی به دست آوردن تور اویلر که همه این مسایل با داشتن گراف مؤلفه‌های قویا همبند، در (|O(|E قابل حل است. | ## جمع‌بندی | علاوه بر این مسئله مؤلفه‌های قویا همبند در مخابرات و شبکه نیز بسیار کاربرد دارد.