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

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

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

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

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

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

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

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