الگوریتم کساراجو الگوریتمی است که به منظور پیدا کردن مولفه های قویا همبند در یک گراف جهت دار استفاده می شود. این الگوریتم توسط سامباسیوا کساراجو در سال ۱۹۷۸ در یک مقاله ارائه شد. کساراجو این الگوریتم را با استفاده از این نکته که مؤلفه های قویا همبند در یک گراف جهت دار با مؤلفه های قویا همبند در معکوس آن گراف جهت دار برابر هستند، ارائه کرد. الگوریتم دیگری که بر پایه همین الگوریتم است، الگوریتم تارجان است که در واقع نسخهٔ بهبودیافته الگوریتم کساراجو است. در حدود ۲۰ سال بعد یعنی در سال ۱۹۹۶ نسخهٔ بهبودیافتهٔ دیگری از این الگوریتم، توسط هارولد گابو منتشر شد.
• گراف قویا همبند
به گرافی گویند که هر جفت راس آن از یکدیگر قابل دسترس باشد. مانند شکل زیر:
• مؤلفه قویا همبند:
مولفه قویا همبند یک گراف به بیشینه زیرمجموعه ای از رأس ها گویند که قویا همبند هستند. یعنی از هر جفت راس در آن مجموعه به یکدیگر مسیر مستقیم وجود دارد. مانند شکل زیر:
• گراف معکوس:
گراف معکوس یا همان GT که در آن راس u به راس v یال دارد اگر و فقط اگر در گراف G راس v به راس u یال داشته باشد. یعنی مجموعه یال های آن به صورت زیر است:
{ ET = { ( u, v ) | ( v, u ) ∈ E
مانند شکل زیر:
این الگوریتم از یک نکتهٔ بسیار ساده استفاده می کند و آن این است که مؤلفه های قویا همبند یک گراف جهت دار با مؤلفه های قویا همبند معکوس آن گراف جهت دار یکی است، این نکته پایهٔ اصلی این الگوریتم است.
ابتدا یک پشته خالی در نظر می گیریم. گراف جهت دار داده شده را، G در نظر می گیریم. این گراف را پیمایش می کنیم. پیمایش این گراف را از یک راس دلخواه به وسیلهٔ یکی از الگوریتم های پیمایش گراف یعنی جستجوی عمق اول انجام می دهیم. وقتی الگوریتم جستجوی عمق اول کار خود را با یک راس به اتمام رساند، آن را در داخل پشته قرار می دهیم. به همین ترتیب ادامه می دهیم تا کل گراف پیمایش شود. در این مرحله تمامی رأس ها در داخل پشته قرار دارند. سپس گراف معکوس G یعنی GT را به دست می آوریم. این بار گراف معکوس را با توجه به اولویت رأس ها در پشته، پیمایش می کنیم. به این ترتیب که در ابتدا از راسی شروع می کنیم که در بالای پشته قرار دارد. فرض کنید راس v در بالای پشته است. جستجوی عمق اول را از آن راس شروع می کنیم. فرض کنید در راسی به نام w به پایان برسد. تمام راس هایی که در این بین ملاقات شده جزو یک مؤلفه های قویا همبند هستند. تمام رأس های ملاقات شده را از پشته خارج و همین الگوریتم را بر روی راسی که در بالای پشته قرار دارد، تکرار می کنیم، تا زمانی که پشته خالی شود.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلف• گراف قویا همبند
به گرافی گویند که هر جفت راس آن از یکدیگر قابل دسترس باشد. مانند شکل زیر:
• مؤلفه قویا همبند:
مولفه قویا همبند یک گراف به بیشینه زیرمجموعه ای از رأس ها گویند که قویا همبند هستند. یعنی از هر جفت راس در آن مجموعه به یکدیگر مسیر مستقیم وجود دارد. مانند شکل زیر:
• گراف معکوس:
گراف معکوس یا همان GT که در آن راس u به راس v یال دارد اگر و فقط اگر در گراف G راس v به راس u یال داشته باشد. یعنی مجموعه یال های آن به صورت زیر است:
{ ET = { ( u, v ) | ( v, u ) ∈ E
مانند شکل زیر:
این الگوریتم از یک نکتهٔ بسیار ساده استفاده می کند و آن این است که مؤلفه های قویا همبند یک گراف جهت دار با مؤلفه های قویا همبند معکوس آن گراف جهت دار یکی است، این نکته پایهٔ اصلی این الگوریتم است.
ابتدا یک پشته خالی در نظر می گیریم. گراف جهت دار داده شده را، G در نظر می گیریم. این گراف را پیمایش می کنیم. پیمایش این گراف را از یک راس دلخواه به وسیلهٔ یکی از الگوریتم های پیمایش گراف یعنی جستجوی عمق اول انجام می دهیم. وقتی الگوریتم جستجوی عمق اول کار خود را با یک راس به اتمام رساند، آن را در داخل پشته قرار می دهیم. به همین ترتیب ادامه می دهیم تا کل گراف پیمایش شود. در این مرحله تمامی رأس ها در داخل پشته قرار دارند. سپس گراف معکوس G یعنی GT را به دست می آوریم. این بار گراف معکوس را با توجه به اولویت رأس ها در پشته، پیمایش می کنیم. به این ترتیب که در ابتدا از راسی شروع می کنیم که در بالای پشته قرار دارد. فرض کنید راس v در بالای پشته است. جستجوی عمق اول را از آن راس شروع می کنیم. فرض کنید در راسی به نام w به پایان برسد. تمام راس هایی که در این بین ملاقات شده جزو یک مؤلفه های قویا همبند هستند. تمام رأس های ملاقات شده را از پشته خارج و همین الگوریتم را بر روی راسی که در بالای پشته قرار دارد، تکرار می کنیم، تا زمانی که پشته خالی شود.
wiki: الگوریتم کساراجو