الگوریتم کساراجو

الگوریتم

این الگوریتم از یک نکتهٔ بسیار ساده استفاده می‌کند و آن این است که مؤلفه‌های قویا همبند یک گراف جهت‌دار با مؤلفه‌های قویا همبند معکوس آن گراف جهت‌دار یکی است، این نکته پایهٔ اصلی این الگوریتم است.
ابتدا یک پشته خالی در نظر می‌گیریم. گراف جهت‌دار داده شده را، G در نظر می‌گیریم.
این گراف را پیمایش می‌کنیم. پیمایش این گراف را از یک راس دلخواه به وسیلهٔ یکی از الگوریتم‌های پیمایش گراف یعنی جستجوی عمق اول انجام می‌دهیم. وقتی الگوریتم جستجوی عمق اول
کار خود را با یک راس به اتمام رساند، آن را در داخل پشته قرار می‌دهیم. به همین ترتیب ادامه می‌دهیم تا کل گراف پیمایش شود.

در این مرحله تمامی رأس‌ها در داخل پشته قرار دارند.

سپس گراف معکوس G یعنی Gᵀ را به دست می‌آوریم. این بار گراف معکوس را با توجه به اولویت رأس‌ها در پشته، پیمایش می‌کنیم. به این ترتیب که در ابتدا از راسی شروع می‌کنیم که در بالای پشته
قرار دارد. فرض کنید راس v در بالای پشته است. جستجوی عمق اول را از آن راس شروع می‌کنیم. فرض کنید در راسی به نام w به پایان برسد. تمام راس‌هایی که در این بین ملاقات شده جزو یک مؤلفه‌های قویا همبند هستند. تمام رأس‌های ملاقات شده را از پشته خارج و همین الگوریتم را بر روی راسی که در بالای پشته قرار دارد، تکرار می‌کنیم، تا زمانی که پشته خالی شود.

مثال

برای درک بیشتر الگوریتم مثال زیر را در نظر بگیرید.
فرض کنید می‌خواهیم مؤلفه‌های قویا همبند را در گراف شکل زیر پیدا کنیم.
ابتدا گراف مورد نظر را با استفاده از الگوریتم جستجوی عمق اول با شروع از راس A پیمایش می‌کنیم.

مطابق آن‌چه در توضیح الگوریتم گفتیم بعد از اجرای جستجوی عمق اول بر روی گراف از راس A، راس H وارد پشته می‌شود.
به این خاطر که جستجوی عمق اول در راس H متوقف می‌شود. بعد از آن، به ترتیب رأس‌های F - E - C - G وارد پشته می‌شوند. سپس جستجوی عمق اول بار دیگر از A
ادامه پیدا کرده و در انتها، پشته به صورت زیر پر می‌شود:

سر پشته --> [H, G, C, E, F, D, B, A]

پس از آن معکوس گراف را محاسبه می‌کنیم. معکوس گراف مورد نظر مطابق شکل زیر است:
حال مطابق آنچه در توضیح الگوریتم گفته شد، جستجوی عمق اول را بر روی گراف معکوس، با شروع از راسی که در سر پشته است (یعنی A)، اجرا می‌کنیم. با پیمایش گراف
از راس A، تنها دو راس B و D ملاقات می‌شوند؛ بنابراین ۳ راس A و B و D، تشکیل یک مؤلفهٔ قویا همبند می‌دهند. پس کافی است این ۳ راس را mark کرده (از پشته و گراف خارج کنیم)
و الگوریتم را ادامه دهیم. راس F اکنون سر پشته است و قبلاً ملاقات (mark) نشده‌است. پس الگوریتم جستجوی عمق اول را بر روی آن اجرا می‌کنیم
و F و E را به عنوان یک مؤلفهٔ قویا همبند دیگر، گزارش می‌کنیم. با ادامه الگوریتم H و G و C نیز که در پشته باقی‌مانده‌اند، به عنوان آخرین مؤلفهٔ قویا همبند
گزارش می‌کنیم.

تعریف

به ازای هر زیر مجموعه‌ای از رأس‌ها مانند U:
f(U) = max u∈U { f(u) }

نتیجه

یک نتیجه حاصل از این لم، این است که اگر در گراف G، داشته باشیم (f(C₁ بزرگتر از (f(C₂، در گراف معکوس یعنی Gᵀ، برعکس خواهد بود و (f(C₁ کوچکتر از (f(C₂ خواهد بود.
چون مؤلفه‌های قویا همبند در G و Gᵀ برابر هستند و تنها جهت یال‌ها عوض خواهد شد.

بنابراین چون این الگوریتم در ابتدا (f(uها را محاسبه می‌کند و سپس در Gᵀ، الگوریتم جستجوی عمق اول را از راسی که بیشینه (f(u را در گراف G دارد، اجرا می‌کند، این راس یعنی
u مطابق نتیجه‌ای که در بالا گرفته شد، دارای کمینه (f(u است.

به این ترتیب، اگر مؤلفه‌ای که u در آن وجود دارد را C₃ بنامیم، الگوریتم جستجوی عمق اول در ابتدا تمامی همسایگان u را در C₃ ملاقات می‌کند. حال ادعا می‌کنیم که جستجوی عمق اول در این مرحله به پایان می‌رسد. چون در غیر این صورت باید از C3 به یکی دیگر از مؤلفه‌ها مانند Ci یال وجود داشته باشد. درحالیکه از C₃ به هیچ مؤلفه دیگری مانند Ci، یال وجود ندارد. چون اگر یالی از یک راس در C₃ به
یک راس در مؤلفه دیگر مانند Cᵢ وجود داشت، طبق لم بالا، (f(C₃ از (f(Cᵢ بزرگتر بود که این با کمینه بودن (f(C₃ تناقض است؛ بنابراین الگوریتم به درستی اولین مؤلفه قویا همبند را مشخص کرد. در مرحله بعد (f(Cᵢ به گونه‌ای انتخاب می‌شود که در گراف G، از (f(C مربوط به تمامی مؤلفه‌ها به جز (f(C₃ بزرگتر است.
به این ترتیب الگوریتم به درستی کار خود را به پایان می‌برد.

پیاده‌سازی

شبه‌کد الگوریتم کساراجو به صورت زیر است:
 1 Algorithm Kosaraju(G,v)
 2 Input: G=(V,E),)
 3 Output: strongly connected component (SCC)
 4 begin
 5 while(stack does not contain all vertices)
 6 Choose an arbitrary vertex v not in S
 7 Depth First Search(G,V)
 8 Each time that depth-first search finishes expanding a vertex u, push u onto S
 9 compute Gᵀ
10 While(stack is not empty)
11 pop vertex v form stack
12 Depth First Search(Gᵀ,v)
13 Output set of visited vertices as a seprate SCC
14 mark this set of vertices form stack and graph
12 end
پیاده‌سازی الگوریتم با استفاده از جاوا:
import java.util.ArrayList;public class Kosaraju {

   private ArrayList<Node> stack;

   public ArrayList<ArrayList<Node>> getSCC(Node root, AdjacencyList list){
       stack = new ArrayList<Node>();

       // search the graph (depth-first search), adding nodes to the stack
       search(root, list, true);

       // reverse all the edges in the graph
       list.reverseGraph();

       // search the graph again in the stack's order
       ArrayList<ArrayList<Node>> SCC = new ArrayList<ArrayList<Node>>();
       while(!stack.isEmpty()){
           ArrayList<Node> component = new ArrayList<Node>();
           search(stack.get(0), list, false);

           // any components we visited are strongly connected
           // remove them from the stack and add them to the component
           for(Iterator<Node> it = stack.iterator(); it.hasNext(); ){
               Node n = it.next();
               if(!n.visited){
                   component.add(n);
                   it.remove();
               }
           }

           // add the component to the result set
           SCC.add(component);
       }
       return SCC;
   }

   private void search(Node root, AdjacencyList list, boolean forward){
       root.visited = forward;
       if(list.getAdjacent(root) == null){
           if(forward) stack.add(0, root);
           return;
       }
       for(Edge e : list.getAdjacent(root)){
           if(e.to.visited != forward){
               search(e.to, list, forward);
           }
       }
       if(forward) stack.add(0, root);
   }}