الگوریتم به عنوان ورودی [[گراف جهت دار|گراف جهت داری]] را میگیرد، و افرازی از رئوس گراف به مؤلفههای قویاً همبند تولید میکند. هر راسی (گره) از گراف، دقیقاً یک بار در مؤلفههای همبند ظاهر میشود. هر راسیراس که در یک دور جهت دار نیست، خودش به عنوان یک مؤلفههای قویاً همبند انتخاب میشود: برای مثال، راسی که درجه ورودی و درجه خروجی آن صفر باشد، یا هر راس از گراف بدون دور به تنهایی یک مؤلفهٔ قویاً همبند حساب میشوند.
ایدهی ابتدایی این الگوریتم: [[الگوریتم جستجو]] عمق اول با گرهٔراس دلخواه شروع میکند (و جستجوی بعدی عمق اول، بر روی گرههاییراسهایی اعمال میشود که دیده نشدهاند). با الگوریتم جستجوی عمق اول، جستجوجستجو، هر گرهیراسی گراف را دقیقاً یک بار میبیند؛ بنابراین، مجموعهیمجموعه ی درخت جستجو، یک جنگل پوشا از گراف است. مؤلفههای قویاً همبند، به عنوان زیردرختهای معین این [[درخت پوشا]]، به دست خواهد آمد. ریشهی این زیردرختها را، ریشهی مؤلفههای قویاً همبند میگویند. هر گرهایراسی از مؤلفههای قویاً همبند ممکن است به عنوان ریشه به کار گرفته شود، اگر اولین گرهایراسی باشد که از آن مؤلفه دیده میشود.
=== پشته ثابت ===
گرههاراسها به ترتیبی که دیده میشوند در داخل [[پشته]] جای میگیرند. زمانی که جستجوی عمق اول به صورت بازگشتی، گرهیراسی V و فرزاندانش را ملاقات کند، آن گرهها،راسها، نباید تا قبل از بازگشت این فراخوانی بازگشتی از پشته، POP شوند. خاصیت یکسانی (ثابت)، این است که، یک گرهبعدراس بعد از پیمایش، بر روی پشته باقی میماند، اگر و تنها اگر مسیری به برخی از گرههایراسهای پایینتر در پشه وجود داشته باشد.
بعد از اتمام فراخوانی ای که V و فرزاندان آن را پیدا میکند، ما میدانیم که آیا V به هر گرهیراسی قبل از خودش در پشته مسیر دارد یا خیر. اگر چنین بود فراخوانی بازمیگردد. V را در پشته به عنوان ثابت، نگاه میدارد. اگر نه، V باید ریشهی مؤلفههای قویاً همبند باشد که شامل V و گرههایراسهای بعدی در پشته است. (گرههاییراسهایی که به V مسیر دارند ولی به ماقبل V مسیری ندارند). تمام مؤلفهها، POP میشود و ثابت را نگه میدارد.
=== پیادهسازی ===
هر گرهیراسی v به یک [[عدد صحیح]]، v.index اختصاص داده میشود که اعداد گرههاراسها بصوت متوالی، بترتیبی که پیدا شدهاند، قرار داده میشود. همچنین یک مقدار، v.lowlink که کوچکترین اندیس هر گرهیراسی شناخته شدهی قابل دسترس از v، شامل خود v را نمایش میدهد، نگه داشته میشود؛ بنابراین، v باید سمت چپ پشته باشد اگر v.lowlinke <v.index در حالی که، v باید به عنوان ریشه مؤلفه قویاً همبند حذف شود اگر v.lowlink==v.index. مقدار v.lowlink، در حین جستجوی عمق اول از v محاسبه میشود، همانطور که گرههایراسهای قابل دسترس از v را پیدا میکند.
== شبه کد ==
خط ۶۹:
</div>
index variable همان شماره راس (گره) در [[الگوریتم جستجوی اول عمق]] میباشد. S پشتهٔ گرههاراسها میباشد که در ابتدا خالی میباشد و برای ذخیرهسازی گرههاییراسهایی که دیده شدهاند ولی هنوز به مؤلفههای قویاً همبند ملحق نشدهاند میباشد. ذکر این نکته مهم است که این پشته همان پشتهٔ جستجوی اول عمق نمیباشد در واقع با خروج آن گرهراس در الگوریتم جستجوی اول عمق از پشته حذف نمیشود و تنها در صورتی گرههاراسها حذف میشوند که یک مؤلفهٔ قویاً همبند پیدا شود تا تمامی رأسهای آن حذف شود.
بیرونیترین حلقه در کد بالا در بین گرههاییراسهایی که هنوز دیده نشدهاند جستجو میکند تا تضمین کند که گرههاییراسهایی که از گرهراس اول قابل دسترسی نیستند نیز دیده خواهند شد. تابع strongconnect یک جستجوی اول عمق را انجام میدهد که تمامی فرزندان راس v را میبیند و تمامی مؤلفههای قویاً همبند آن زیر گراف را پیدا میکند.
هنگامی که هر گرهایراسی [[تابع بازگشتی]] جستجوی اول عمقش تمام میشود اگر مقدار lowlink آن برابر اندیس آن باشد یعنی آن راس ریشهٔ یک مؤلفهٔ قویاً همبند شامل تمام گرههایراسهای بالاتر از آن درون پشته خواهد بود. الگوریتم تمامی گرههایراسهای بالاتر از انرا از پشته خارج میکند و همهٔ آنهارا به عنوان یک مؤلفه در نظر میگیرد.