الگوریتم تارژان ( نامگذاری: مبدع، رابرت تارژان ) ، از الگوریتم های تئوری گراف است که برای پیدا کردن مؤلفه های قویاً همبند در یک گراف استفاده می شود. با وجود اینکه، این الگوریتم از نظر زمانی مقدم بوده است، می توان دید که نسخهٔ بهبود یافته الگوریتم کساراجو و از نظر کارایی ( بازده ) با الگوریتم مؤلفه قوی مبتنی بر مسیر قابل مقایسه است.
الگوریتم به عنوان ورودی گراف جهت داری را می گیرد، و افرازی از رئوس گراف به مؤلفه های قویاً همبند تولید می کند. هر راسی ( گره ) از گراف، دقیقاً یک بار در مؤلفه های همبند ظاهر می شود. هر راس که در یک دور جهت دار نیست، خودش به عنوان یک مؤلفه های قویاً همبند انتخاب می شود: برای مثال، راسی که درجه ورودی و درجه خروجی آن صفر باشد، یا هر راس از گراف بدون دور به تنهایی یک مؤلفهٔ قویاً همبند حساب می شوند. ایدهی ابتدایی این الگوریتم: الگوریتم جستجو عمق اول با راس دلخواه شروع می کند ( و جستجوی بعدی عمق اول، بر روی راس هایی اعمال می شود که دیده نشدهاند ) . با الگوریتم جستجوی عمق اول، جستجو، هر راسی گراف را دقیقاً یک بار می بیند؛ بنابراین، مجموعه ی درخت جستجو، یک جنگل پوشا از گراف است. مؤلفه های قویاً همبند، به عنوان زیردرختهای معین این درخت پوشا، به دست خواهد آمد. ریشهی این زیردرختها را، ریشهی مؤلفه های قویاً همبند می گویند. هر راسی از مؤلفه های قویاً همبند ممکن است به عنوان ریشه به کار گرفته شود، اگر اولین راسی باشد که از آن مؤلفه دیده می شود.
راس ها به ترتیبی که دیده می شوند در داخل پشته جای می گیرند. زمانی که جستجوی عمق اول به صورت بازگشتی، راسی V و فرزاندانش را ملاقات کند، آن راس ها، نباید تا قبل از بازگشت این فراخوانی بازگشتی از پشته، POP شوند. خاصیت یکسانی ( ثابت ) ، این است که، یک راس بعد از پیمایش، بر روی پشته باقی می ماند، اگر و تنها اگر مسیری به برخی از راس های پایین تر در پشه وجود داشته باشد. بعد از اتمام فراخوانی ای که V و فرزاندان آن را پیدا می کند، ما می دانیم که آیا V به هر راسی قبل از خودش در پشته مسیر دارد یا خیر. اگر چنین بود فراخوانی بازمی گردد. V را در پشته به عنوان ثابت، نگاه می دارد. اگر نه، V باید ریشهی مؤلفه های قویاً همبند باشد که شامل V و راس های بعدی در پشته است. ( راس هایی که به V مسیر دارند ولی به ماقبل V مسیری ندارند ) . تمام مؤلفه ها، POP می شود و ثابت را نگه می دارد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفالگوریتم به عنوان ورودی گراف جهت داری را می گیرد، و افرازی از رئوس گراف به مؤلفه های قویاً همبند تولید می کند. هر راسی ( گره ) از گراف، دقیقاً یک بار در مؤلفه های همبند ظاهر می شود. هر راس که در یک دور جهت دار نیست، خودش به عنوان یک مؤلفه های قویاً همبند انتخاب می شود: برای مثال، راسی که درجه ورودی و درجه خروجی آن صفر باشد، یا هر راس از گراف بدون دور به تنهایی یک مؤلفهٔ قویاً همبند حساب می شوند. ایدهی ابتدایی این الگوریتم: الگوریتم جستجو عمق اول با راس دلخواه شروع می کند ( و جستجوی بعدی عمق اول، بر روی راس هایی اعمال می شود که دیده نشدهاند ) . با الگوریتم جستجوی عمق اول، جستجو، هر راسی گراف را دقیقاً یک بار می بیند؛ بنابراین، مجموعه ی درخت جستجو، یک جنگل پوشا از گراف است. مؤلفه های قویاً همبند، به عنوان زیردرختهای معین این درخت پوشا، به دست خواهد آمد. ریشهی این زیردرختها را، ریشهی مؤلفه های قویاً همبند می گویند. هر راسی از مؤلفه های قویاً همبند ممکن است به عنوان ریشه به کار گرفته شود، اگر اولین راسی باشد که از آن مؤلفه دیده می شود.
راس ها به ترتیبی که دیده می شوند در داخل پشته جای می گیرند. زمانی که جستجوی عمق اول به صورت بازگشتی، راسی V و فرزاندانش را ملاقات کند، آن راس ها، نباید تا قبل از بازگشت این فراخوانی بازگشتی از پشته، POP شوند. خاصیت یکسانی ( ثابت ) ، این است که، یک راس بعد از پیمایش، بر روی پشته باقی می ماند، اگر و تنها اگر مسیری به برخی از راس های پایین تر در پشه وجود داشته باشد. بعد از اتمام فراخوانی ای که V و فرزاندان آن را پیدا می کند، ما می دانیم که آیا V به هر راسی قبل از خودش در پشته مسیر دارد یا خیر. اگر چنین بود فراخوانی بازمی گردد. V را در پشته به عنوان ثابت، نگاه می دارد. اگر نه، V باید ریشهی مؤلفه های قویاً همبند باشد که شامل V و راس های بعدی در پشته است. ( راس هایی که به V مسیر دارند ولی به ماقبل V مسیری ندارند ) . تمام مؤلفه ها، POP می شود و ثابت را نگه می دارد.
