در یک گراف جهت‌دار، یک مؤلفه‌ی قویاً همبند زیرگرافی است که از هر رأس آن به هر رأس دیگر یال باشد و نتوان رأس دیگری را به آن اضافه کرد که این خاصیت برقرار بماند.

برای به دست آوردن مؤلفه‌های قویاً همبند گراف، الگوریتم پیمایش عمقی گراف را اجرا می‌کنیم و هر بار که به رأسی می‌رسیم که همسایه‌های آن دیده شده‌اند یا همسایه‌ای ندارد، آن را درون یک پشته (یا در پیاده‌سازی، یک آرایه) ذخیره می‌کنیم. ترانهاده‌ی این گراف را محاسبه می‌کنیم و رأسها را به ترتیب خروج از پشته (عکس آرایه) طی می‌کنیم و رأسهای متصل به آنها را با پیمایش گراف به دست می‌آوریم و در یک مؤلفه قرار می‌دهیم و از بقیه گراف حذف می‌کنیم.

زمان این الگوریتم اگر گراف با لیست مجاورت پیاده‌سازی شده باشد $O(|V|+|E|)$ و اگر گراف با ماتریس مجاورت پیاده‌سازی شده باشد $O(|V|^2)$ است.

توضیحات بیشتر این الگوریتم

الگوریتم‌های دیگر این مسأله

دور اویلری دوری است که از همه‌ی یالهای گراف عبور می‌کند. برای اینکه گرافی دور اویلری داشته باشد باید درجه‌ی همه‌ی رأسهای آن زوج باشد. الگوریتمی که برای پیدا کردن دور اویلری به کار می‌رود، هر بار یک دور در گراف پیدا می‌کند و آن را با حذف کردن یالهای آن از گراف حذف می‌کند. گراف باقیمانده همچنان اویلری است. با به هم چسباندن این دورها یک دور اویلری به دست می‌آید.

الگوریتم پیدا کردن دور

اگر گراف دارای حداکثر ۲ رأس درجه فرد باشد، مسیر اویلری دارد. برای به دست آوردن مسیر اویلری، از یک رأس درجه فرد (یا اگر چنین رأسی نیست یک رأس دلخواه) شروع می‌کنیم و یالهای مجاور این رأس که حذف آن باعث ناهمبند شدن گراف نمی‌شود طی می‌کنیم (مگر اینکه چنین یالی نباشد که در این صورت همان تنها یال موجود را طی می‌کنیم) و سپس آن را حذف می‌کنیم. در پایان این کار یک مسیر اویلری به دست می‌آید.

البته همان الگوریتم دور اویلری در زمان بهتری این مسأله را حل می‌کند.

الگوریتم پیدا کردن مسیر اویلری