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

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

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

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

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

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

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

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