الگوریتم تارژان مؤلفه‌های قویا همبند

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
الگوریتم تارژان مؤلفه‌های قویا همبند
تجسم الگوریتم تارژان مؤلفه‌های قویا همبند
تجسم الگوریتم تارژان مؤلفه‌های قویا همبند
ساختمان داده‌ها گراف
عملکرد بدترین حالت

الگوریتم تارژان (نامگذاری: مبدع، رابرت تارژان)، از الگوریتم‌های تئوری گراف است که برای پیدا کردن مولفه‌های قویاً همبند در یک گراف استفاده می‌شود. با وجود اینکه، این الگوریتم از نظر زمانی مقدم بوده است، می‌توان دید که نسخهٔ بهبود یافته الگوریتم کساراجو و از نظر کارایی (بازده) با الگوریتم مؤلفه قوی مبتنی بر مسیر قابل مقایسه است.

نمای کلی[ویرایش]

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

پشته ثابت[ویرایش]

گره‌ها به ترتیبی که دیده می‌شوند در داخل پشته جای می‌گیرند. زمانی که جستجوی عمق اول به صورت بازگشتی، گرهی 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 را پیدا می‌کند.

شبه کد[ویرایش]

algorithm tarjan is
input: graph G = (V, E)
output: set of strongly connected components (sets of vertices)
index := ۰
S := empty
for each v in V do

if (v.index is undefined) then

 strongconnect(v)
 end if
end for
function strongconnect(v)
  // Set the depth index for v to the smallest unused index
 v.index := index
 v.lowlink := index
 index := index + 1
 S.push(v)
  // Consider successors of v
 for each (v, w) in E do
 if (w.index is undefined) then
    // Successor w has not yet been visited; recurse on it
 strongconnect(w)
 v.lowlink := min(v.lowlink, w.lowlink)
 else if (w is in S) then
    // Successor w is in stack S and hence in the current SCC
 v.lowlink := min(v.lowlink, w.index)
 end if
 end for
  // If v is a root node, pop the stack and generate an SCC
 if (v.lowlink = v.index) then
 start a new strongly connected component
 repeat
 w := S.pop()
 add w to current strongly connected component
 until (w = v)
 output the current strongly connected component
 end if
end function

index variable همان شماره راس در الگوریتم جستجوی اول عمق می‌باشد. S پشتهٔ گره‌ها می‌باشد که در ابتدا خالی می‌باشد و برای ذخیره‌سازی گره‌هایی که دیده شده‌اند ولی هنوز به مولفه‌های قویاً همبند ملحق نشده‌اند می‌باشد. ذکر این نکته مهم است که این پشته همان پشتهٔ جستجوی اول عمق نمی‌باشد در واقع با خروج آن گره در الگوریتم جستجوی اول عمق از پشته حذف نمی‌شود و تنها در صورتی گره‌ها حذف می‌شوند که یک مولفهٔ قویاً همبند پیدا شود تا تمامی راس‌های آن حذف شود. بیرونی‌ترین حلقه در کد بالا در بین گره‌هایی که هنوز دیده نشده‌اند جستجو می‌کند تا تضمین کند که گره‌هایی که از گره اول قابل دسترسی نیستند نیز دیده خواهند شد. تابع strongconnect یک جستجوی اول عمق را انجام می‌دهد که تمامی فرزندان راس v را می‌بیند و تمامی مولفه‌های قویاً همبند آن زیر گراف را پیدا می‌کند. هنگامی که هر گره‌ای تابع بازگشتی جستجوی اول عمقش تمام می‌شود اگر مقدار lowlink آن برابر اندیس آن باشد یعنی آن راس ریشهٔ یک مولفهٔ قویاً همبند شامل تمام گره‌های بالاتر از آن درون پشته خواهد بود. الگوریتم تمامی گره‌های بالاتر از انرا از پشته خارج می‌کند و همهٔ آنهارا به عنوان یک مولفه در نظر می‌گیرد.

منابع[ویرایش]