Kosarajuمقاله

الگوریتم Kosaraju چیست و اصلاً چه مشکلی را حل می‌کند؟

در این مقاله از صفر با الگوریتم Kosaraju آشنا می‌شویم؛ الگوریتمی برای پیدا کردن مؤلفه‌های قویاً همبند در گراف‌های جهت‌دار. بدون ورود سنگین به ریاضیات، ابتدا مسئله را می‌فهمیم، سپس ایده اصلی الگوریتم و کاربردهای واقعی آن را بررسی می‌کنیم.

۲۸ مرداد ۱۴۰۵9 دقیقه مطالعه4 بازدید

#Kosaraju#Graph Algorithms#Strongly Connected Components#SCC#DFS#Algorithms#Directed Graph#Software Engineering

Arian Soleimanzadeh

Software Engineer & Researcher

تصویر مفهومی الگوریتم Kosaraju و مؤلفه‌های قویاً همبند در یک گراف جهت‌دار

Arian Soleimanzadeh

هوش مصنوعی · کد · محصول

پژوهش + مهندسی

در این صفحه

مقدمه

بسیاری از الگوریتم‌های گراف در نگاه اول پیچیده به نظر می‌رسند، اما معمولاً پشت آن‌ها یک مسئله بسیار ساده و قابل لمس قرار دارد. الگوریتم Kosaraju نیز یکی از همین الگوریتم‌هاست.

Kosaraju برای پیدا کردن Strongly Connected Components یا به اختصار SCC در یک گراف جهت‌دار استفاده می‌شود.

اگر این اصطلاحات برایتان ناآشنا هستند، نگران نباشید. در این مقاله قرار نیست مستقیماً وارد فرمول‌های پیچیده یا پیاده‌سازی الگوریتم شویم. ابتدا از خود مسئله شروع می‌کنیم و می‌بینیم چرا اصلاً چنین الگوریتمی لازم است.

قبل از Kosaraju، گراف چیست؟

گراف را می‌توان مجموعه‌ای از گره‌ها یا Vertexها و ارتباط میان آن‌ها در نظر گرفت.

برای مثال، فرض کنید چهار کاربر در یک شبکه اجتماعی داریم:

Code

A --- B
|     |
C --- D

هر حرف یک کاربر است و خطوط میان آن‌ها نشان‌دهنده یک ارتباط هستند.

در علوم کامپیوتر از گراف‌ها برای مدل‌سازی بسیاری از سیستم‌های واقعی استفاده می‌شود، از جمله:

شبکه‌های اجتماعی
مسیرهای بین شهرها
ارتباط بین سرورها
وابستگی بین پکیج‌های نرم‌افزاری
لینک‌های بین صفحات وب
جریان اجرای برنامه
ارتباط بین سرویس‌های یک سیستم توزیع‌شده

بنابراین گراف فقط یک مفهوم تئوری نیست؛ بلکه یکی از مهم‌ترین مدل‌های مورد استفاده در مهندسی نرم‌افزار است.

گراف جهت‌دار چیست؟

در بعضی گراف‌ها ارتباط دوطرفه است، اما در بسیاری از مسائل واقعی ارتباط دارای جهت است.

برای مثال:

Code

A → B

یعنی از A می‌توان به B رفت، اما الزاماً از B نمی‌توان به A برگشت.

چنین گرافی را Directed Graph یا گراف جهت‌دار می‌نامیم.

مثلاً در یک شبکه اجتماعی:

Code

Ali → Sara

می‌تواند به این معنی باشد که Ali، Sara را Follow کرده است. این اتفاق الزاماً به معنی Follow کردن Ali توسط Sara نیست.

در نرم‌افزار نیز ممکن است داشته باشیم:

Code

Service A → Service B

یعنی سرویس A به سرویس B وابسته است یا از آن استفاده می‌کند.

مسئله اصلی از کجا شروع می‌شود؟

فرض کنید گراف زیر را داریم:

Code

A → B → C
↑       ↓
└───────┘

D → E

در بخش اول گراف می‌توانیم از A به B برویم، از B به C و از C دوباره به A برگردیم.

پس بین A، B و C نوعی ارتباط بسیار قوی وجود دارد.

اگر از هرکدام از این سه گره شروع کنیم، می‌توانیم به دو گره دیگر برسیم.

اما D و E چنین وضعیتی ندارند. از D می‌توان به E رسید، ولی از E مسیری برای بازگشت به D وجود ندارد.

بنابراین می‌توانیم بگوییم:

Code

{A, B, C}

یک گروه خاص از گره‌ها را تشکیل می‌دهد.

این گروه همان چیزی است که در نظریه گراف به آن Strongly Connected Component می‌گوییم.

Strongly Connected یعنی چه؟

دو رأس u و v در یک گراف جهت‌دار قویاً همبند هستند اگر:

Code

u → ... → v

مسیر داشته باشد و هم‌زمان:

Code

v → ... → u

نیز مسیر وجود داشته باشد.

یعنی هرکدام بتواند به دیگری برسد.

برای مثال:

Code

A → B
↑   ↓
└── C

اگر مسیرها به شکلی باشند که:

Code

A → B
B → C
C → A

آن‌گاه هر سه گره در یک SCC قرار دارند.

از A می‌توان به C رسید، از C می‌توان به B رسید و به همین شکل همه گره‌ها از طریق یک یا چند یال به یکدیگر دسترسی دارند.

Strongly Connected Component چیست؟

یک Strongly Connected Component یا SCC، بزرگ‌ترین مجموعه‌ای از رأس‌ها در یک گراف جهت‌دار است که هر رأس بتواند به تمام رأس‌های دیگر آن مجموعه برسد.

مثلاً:

Code

A → B → C
↑       ↓
└───────┘

D → E → F
↑       ↓
└───────┘

در این گراف دو SCC داریم:

Code

SCC 1 = {A, B, C}
SCC 2 = {D, E, F}

ممکن است بین این دو گروه نیز یالی وجود داشته باشد، اما تا زمانی که امکان رفت و برگشت کامل میان دو گروه وجود نداشته باشد، آن‌ها دو SCC مجزا باقی می‌مانند.

حالا Kosaraju چه کاری انجام می‌دهد؟

کار الگوریتم Kosaraju این است که تمام SCCهای یک گراف جهت‌دار را پیدا کند.

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

ورودی الگوریتم می‌تواند چیزی شبیه این باشد:

Code

A → B
B → C
C → A
C → D
D → E
E → D

و خروجی آن:

Code

SCC 1 = {A, B, C}
SCC 2 = {D, E}

خواهد بود.

پس می‌توان Kosaraju را به شکل ساده این‌طور تعریف کرد:

الگوریتم Kosaraju روشی برای تقسیم یک گراف جهت‌دار به گروه‌هایی است که اعضای هر گروه بتوانند از طریق مسیرهای جهت‌دار به یکدیگر برسند.

چرا پیدا کردن SCCها مهم است؟

ممکن است در ابتدا این مسئله کاملاً تئوری به نظر برسد، اما SCCها در بسیاری از سیستم‌های واقعی کاربرد دارند.

1. پیدا کردن وابستگی‌های حلقوی در نرم‌افزار

فرض کنید سه ماژول داریم:

Code

Module A → Module B
Module B → Module C
Module C → Module A

اینجا یک Circular Dependency ایجاد شده است.

هیچ ماژولی واقعاً مستقل از بقیه نیست و هر سه به شکل مستقیم یا غیرمستقیم به یکدیگر وابسته‌اند.

این سه ماژول یک SCC تشکیل می‌دهند.

با پیدا کردن SCCها می‌توان چنین چرخه‌هایی را در سیستم‌های بزرگ شناسایی کرد.

2. معماری Microserviceها

فرض کنید معماری زیر را داریم:

Code

User Service → Payment Service
Payment Service → Notification Service
Notification Service → User Service

این سه سرویس به یک چرخه وابستگی وارد شده‌اند.

در یک معماری بزرگ با ده‌ها یا صدها سرویس، پیدا کردن این چرخه‌ها به صورت دستی دشوار است.

با مدل کردن سرویس‌ها به صورت گراف و اجرای الگوریتم SCC می‌توان گروه‌های دارای وابستگی چرخه‌ای را تشخیص داد.

3. شبکه‌های اجتماعی

فرض کنید یال A → B نشان دهد که کاربر A کاربر B را دنبال می‌کند.

ممکن است در یک شبکه اجتماعی بزرگ، گروه‌هایی وجود داشته باشند که اعضای آن‌ها از طریق زنجیره‌ای از ارتباطات به یکدیگر دسترسی داشته باشند.

تحلیل SCC می‌تواند برای بررسی ساختار چنین شبکه‌هایی مفید باشد.

البته در سیستم‌های واقعی تحلیل شبکه اجتماعی معمولاً بسیار پیچیده‌تر از اجرای مستقیم یک الگوریتم SCC است، اما Strong Connectivity یکی از مفاهیم پایه در تحلیل شبکه‌ها محسوب می‌شود.

4. تحلیل لینک‌های وب

صفحات وب را نیز می‌توان به صورت یک گراف در نظر گرفت:

Code

Page A → Page B
Page B → Page C
Page C → Page A

هر لینک یک یال جهت‌دار است.

با پیدا کردن SCCها می‌توان بخش‌هایی از وب‌سایت یا شبکه صفحات را پیدا کرد که درون آن‌ها امکان حرکت بین صفحات از طریق لینک‌ها وجود دارد.

5. تحلیل برنامه و Compilerها

در Compiler Design و Static Analysis نیز گراف‌ها بسیار پرکاربرد هستند.

برای مثال:

Control Flow Graph
Call Graph
Dependency Graph

ممکن است دارای cycle باشند.

شناسایی SCCها کمک می‌کند بخش‌هایی از برنامه را که به شکل چرخه‌ای به یکدیگر وابسته هستند پیدا کنیم.

6. سیستم‌های Package Management

فرض کنید وابستگی پکیج‌ها چنین باشد:

Code

Package A → Package B
Package B → Package C
Package C → Package A

این ساختار یک dependency cycle ایجاد می‌کند.

در پروژه‌های بزرگ، گراف وابستگی ممکن است شامل هزاران کتابخانه و ماژول باشد. الگوریتم‌های SCC می‌توانند در تحلیل این ساختارها استفاده شوند.

چرا نمی‌توان فقط از DFS معمولی استفاده کرد؟

ممکن است این سؤال مطرح شود که اگر DFS می‌تواند گراف را پیمایش کند، چرا مستقیماً با DFS گروه‌ها را پیدا نکنیم؟

مشکل اینجاست که در گراف جهت‌دار، Reachability یک‌طرفه به معنی Strong Connectivity نیست.

اگر داشته باشیم:

Code

A → B → C

DFS از A می‌تواند هر سه گره را مشاهده کند.

اما این به معنی SCC بودن آن‌ها نیست.

زیرا از C نمی‌توان به B یا A برگشت.

پس:

Code

Reachable ≠ Strongly Connected

Kosaraju با یک تکنیک هوشمندانه این مشکل را حل می‌کند.

ایده اصلی Kosaraju چیست؟

در این مقاله وارد جزئیات اجرای الگوریتم نمی‌شویم، اما ایده اصلی را می‌توان در سه مرحله خلاصه کرد.

مرحله اول: اجرای DFS

ابتدا DFS روی گراف اصلی اجرا می‌شود و ترتیب پایان پردازش گره‌ها ثبت می‌شود.

مرحله دوم: برعکس کردن جهت تمام یال‌ها

گراف جدیدی می‌سازیم که به آن Transpose Graph گفته می‌شود.

اگر در گراف اصلی داشته باشیم:

Code

A → B

در گراف Transpose خواهیم داشت:

Code

A ← B

مرحله سوم: اجرای دوباره DFS

DFS را دوباره روی گراف Transpose اجرا می‌کنیم، اما این بار گره‌ها را بر اساس ترتیب خاصی که در مرحله اول به دست آورده‌ایم انتخاب می‌کنیم.

هر پیمایش DFS در این مرحله یک SCC را مشخص می‌کند.

به صورت خلاصه:

Code

Original Graph
      ↓
     DFS
      ↓
Finish Order
      ↓
Transpose Graph
      ↓
     DFS
      ↓
     SCCs

دلیل ریاضی اینکه چرا این روش کار می‌کند را در مقاله‌های بعدی این مجموعه بررسی خواهیم کرد.

یک مثال بسیار ساده

گراف زیر را در نظر بگیرید:

Code

A → B → C
↑       ↓
└───────┘

C → D
D → E
E → D

در بخش اول:

Code

A → B → C → A

داریم، پس:

Code

{A, B, C}

یک SCC است.

همچنین:

Code

D → E
E → D

بنابراین:

Code

{D, E}

SCC دیگری است.

هرچند از C می‌توان به D رفت، اما از D یا E نمی‌توان به A، B یا C بازگشت.

پس این دو مجموعه نباید با یکدیگر ادغام شوند.

خروجی Kosaraju برای این گراف خواهد بود:

Code

SCC 1 = {A, B, C}
SCC 2 = {D, E}

پیچیدگی زمانی Kosaraju چقدر است؟

یکی از دلایل مهم کاربردی بودن Kosaraju، کارایی بالای آن است.

با استفاده از Adjacency List، پیچیدگی زمانی الگوریتم برابر است با:

Code

O(V + E)

که در آن:

V تعداد Vertexها یا رأس‌هاست.
E تعداد Edgeها یا یال‌هاست.

یعنی الگوریتم در مقیاس گراف تقریباً خطی عمل می‌کند.

این موضوع باعث می‌شود برای گراف‌های بزرگ نیز گزینه مناسبی باشد.

آیا Kosaraju تنها الگوریتم پیدا کردن SCC است؟

خیر.

الگوریتم‌های معروف دیگری نیز برای پیدا کردن Strongly Connected Components وجود دارند، از جمله:

Tarjan's Algorithm
Gabow's Algorithm

Tarjan نیز دارای پیچیدگی زمانی O(V + E) است و می‌تواند SCCها را با یک DFS اصلی پیدا کند.

Kosaraju معمولاً به دلیل ساختار ساده و قابل فهم خود یکی از بهترین الگوریتم‌ها برای یادگیری مفهوم SCC است.

Kosaraju را چه زمانی باید به خاطر بیاوریم؟

هر زمان مسئله‌ای شامل یک Directed Graph بود و عباراتی مانند موارد زیر مشاهده کردید، احتمالاً باید به SCC فکر کنید:

گروه‌هایی از گره‌ها که همه به یکدیگر دسترسی دارند
Circular Dependency
Mutual Reachability
Cycles between modules
Groups of mutually reachable services
Strong Connectivity
Component decomposition of a directed graph

در چنین شرایطی، Kosaraju یکی از گزینه‌های اصلی حل مسئله است.

تفاوت Cycle و SCC چیست؟

این دو مفهوم مرتبط هستند اما دقیقاً یکسان نیستند.

Cycle یک مسیر بسته است:

Code

A → B → C → A

اما SCC یک مجموعه maximal از گره‌های mutually reachable است.

ممکن است داخل یک SCC چندین cycle مختلف وجود داشته باشد.

بنابراین SCC مفهومی گسترده‌تر از پیدا کردن یک cycle ساده است.

برای یادگیری Kosaraju چه چیزهایی باید بلد باشیم؟

برای فهم کامل این الگوریتم بهتر است با مفاهیم زیر آشنا باشید:

Graph و Directed Graph
Vertex و Edge
Path و Reachability
Depth-First Search یا DFS
Finish Time در DFS
Graph Transpose
Strongly Connected Components

در مقاله‌های بعدی این مجموعه، این مفاهیم را مرحله‌به‌مرحله بررسی خواهیم کرد.

جمع‌بندی

الگوریتم Kosaraju برای پیدا کردن Strongly Connected Components در یک گراف جهت‌دار طراحی شده است.

یک SCC گروهی از گره‌هاست که هر عضو آن می‌تواند از طریق مسیرهای جهت‌دار به تمام اعضای دیگر گروه برسد.

این مسئله در حوزه‌هایی مانند معماری نرم‌افزار، dependency analysis، شبکه‌های اجتماعی، compilerها، microserviceها و تحلیل شبکه‌ها کاربرد دارد.

ایده کلی Kosaraju شامل دو DFS و ساخت Transpose Graph است و با استفاده از Adjacency List در زمان O(V + E) اجرا می‌شود.

اما مهم‌ترین نکته این مقاله این است:

Kosaraju فقط یک الگوریتم برای پیدا کردن cycle نیست؛ بلکه ابزاری برای کشف ساختار داخلی یک گراف جهت‌دار و تقسیم آن به مجموعه‌هایی از گره‌های mutually reachable است.

در مقاله بعدی این مجموعه، مفهوم Strongly Connected Components را عمیق‌تر بررسی می‌کنیم تا قبل از ورود به مراحل اجرایی Kosaraju، دقیقاً بدانیم این الگوریتم به دنبال پیدا کردن چه ساختاری در گراف است.

مقاله قبلی

Longest Common Substring چیست؟ پیدا کردن طولانی‌ترین بخش مشترک دو رشته با Dynamic Programming

مقاله بعدی

فاصله همینگ (Hamming Distance) چیست؟ از مفهوم تا پیاده‌سازی و کاربردهای واقعی

Kosarajuمقاله

الگوریتم Kosaraju چیست و اصلاً چه مشکلی را حل می‌کند؟

۲۸ مرداد ۱۴۰۵9 دقیقه مطالعه4 بازدید

#Kosaraju#Graph Algorithms#Strongly Connected Components#SCC#DFS#Algorithms#Directed Graph#Software Engineering

Arian Soleimanzadeh

Software Engineer & Researcher

Arian Soleimanzadeh

هوش مصنوعی · کد · محصول

پژوهش + مهندسی

در این صفحه

مقدمه

Kosaraju برای پیدا کردن Strongly Connected Components یا به اختصار SCC در یک گراف جهت‌دار استفاده می‌شود.

قبل از Kosaraju، گراف چیست؟

گراف را می‌توان مجموعه‌ای از گره‌ها یا Vertexها و ارتباط میان آن‌ها در نظر گرفت.

برای مثال، فرض کنید چهار کاربر در یک شبکه اجتماعی داریم:

Code

A --- B
|     |
C --- D

هر حرف یک کاربر است و خطوط میان آن‌ها نشان‌دهنده یک ارتباط هستند.

در علوم کامپیوتر از گراف‌ها برای مدل‌سازی بسیاری از سیستم‌های واقعی استفاده می‌شود، از جمله:

شبکه‌های اجتماعی
مسیرهای بین شهرها
ارتباط بین سرورها
وابستگی بین پکیج‌های نرم‌افزاری
لینک‌های بین صفحات وب
جریان اجرای برنامه
ارتباط بین سرویس‌های یک سیستم توزیع‌شده

بنابراین گراف فقط یک مفهوم تئوری نیست؛ بلکه یکی از مهم‌ترین مدل‌های مورد استفاده در مهندسی نرم‌افزار است.

گراف جهت‌دار چیست؟

در بعضی گراف‌ها ارتباط دوطرفه است، اما در بسیاری از مسائل واقعی ارتباط دارای جهت است.

برای مثال:

Code

A → B

یعنی از A می‌توان به B رفت، اما الزاماً از B نمی‌توان به A برگشت.

چنین گرافی را Directed Graph یا گراف جهت‌دار می‌نامیم.

مثلاً در یک شبکه اجتماعی:

Code

Ali → Sara

می‌تواند به این معنی باشد که Ali، Sara را Follow کرده است. این اتفاق الزاماً به معنی Follow کردن Ali توسط Sara نیست.

در نرم‌افزار نیز ممکن است داشته باشیم:

Code

Service A → Service B

یعنی سرویس A به سرویس B وابسته است یا از آن استفاده می‌کند.

مسئله اصلی از کجا شروع می‌شود؟

فرض کنید گراف زیر را داریم:

Code

A → B → C
↑       ↓
└───────┘

D → E

در بخش اول گراف می‌توانیم از A به B برویم، از B به C و از C دوباره به A برگردیم.

پس بین A، B و C نوعی ارتباط بسیار قوی وجود دارد.

اگر از هرکدام از این سه گره شروع کنیم، می‌توانیم به دو گره دیگر برسیم.

اما D و E چنین وضعیتی ندارند. از D می‌توان به E رسید، ولی از E مسیری برای بازگشت به D وجود ندارد.

بنابراین می‌توانیم بگوییم:

Code

{A, B, C}

یک گروه خاص از گره‌ها را تشکیل می‌دهد.

این گروه همان چیزی است که در نظریه گراف به آن Strongly Connected Component می‌گوییم.

Strongly Connected یعنی چه؟

دو رأس u و v در یک گراف جهت‌دار قویاً همبند هستند اگر:

Code

u → ... → v

مسیر داشته باشد و هم‌زمان:

Code

v → ... → u

نیز مسیر وجود داشته باشد.

یعنی هرکدام بتواند به دیگری برسد.

برای مثال:

Code

A → B
↑   ↓
└── C

اگر مسیرها به شکلی باشند که:

Code

A → B
B → C
C → A

آن‌گاه هر سه گره در یک SCC قرار دارند.

Strongly Connected Component چیست؟

مثلاً:

Code

A → B → C
↑       ↓
└───────┘

D → E → F
↑       ↓
└───────┘

در این گراف دو SCC داریم:

Code

SCC 1 = {A, B, C}
SCC 2 = {D, E, F}

حالا Kosaraju چه کاری انجام می‌دهد؟

کار الگوریتم Kosaraju این است که تمام SCCهای یک گراف جهت‌دار را پیدا کند.

ورودی الگوریتم می‌تواند چیزی شبیه این باشد:

Code

A → B
B → C
C → A
C → D
D → E
E → D

و خروجی آن:

Code

SCC 1 = {A, B, C}
SCC 2 = {D, E}

خواهد بود.

پس می‌توان Kosaraju را به شکل ساده این‌طور تعریف کرد:

الگوریتم Kosaraju روشی برای تقسیم یک گراف جهت‌دار به گروه‌هایی است که اعضای هر گروه بتوانند از طریق مسیرهای جهت‌دار به یکدیگر برسند.

چرا پیدا کردن SCCها مهم است؟

ممکن است در ابتدا این مسئله کاملاً تئوری به نظر برسد، اما SCCها در بسیاری از سیستم‌های واقعی کاربرد دارند.

1. پیدا کردن وابستگی‌های حلقوی در نرم‌افزار

فرض کنید سه ماژول داریم:

Code

Module A → Module B
Module B → Module C
Module C → Module A

اینجا یک Circular Dependency ایجاد شده است.

هیچ ماژولی واقعاً مستقل از بقیه نیست و هر سه به شکل مستقیم یا غیرمستقیم به یکدیگر وابسته‌اند.

این سه ماژول یک SCC تشکیل می‌دهند.

با پیدا کردن SCCها می‌توان چنین چرخه‌هایی را در سیستم‌های بزرگ شناسایی کرد.

2. معماری Microserviceها

فرض کنید معماری زیر را داریم:

Code

User Service → Payment Service
Payment Service → Notification Service
Notification Service → User Service

این سه سرویس به یک چرخه وابستگی وارد شده‌اند.

در یک معماری بزرگ با ده‌ها یا صدها سرویس، پیدا کردن این چرخه‌ها به صورت دستی دشوار است.

با مدل کردن سرویس‌ها به صورت گراف و اجرای الگوریتم SCC می‌توان گروه‌های دارای وابستگی چرخه‌ای را تشخیص داد.

3. شبکه‌های اجتماعی

فرض کنید یال A → B نشان دهد که کاربر A کاربر B را دنبال می‌کند.

تحلیل SCC می‌تواند برای بررسی ساختار چنین شبکه‌هایی مفید باشد.

4. تحلیل لینک‌های وب

صفحات وب را نیز می‌توان به صورت یک گراف در نظر گرفت:

Code

Page A → Page B
Page B → Page C
Page C → Page A

هر لینک یک یال جهت‌دار است.

5. تحلیل برنامه و Compilerها

در Compiler Design و Static Analysis نیز گراف‌ها بسیار پرکاربرد هستند.

برای مثال:

Control Flow Graph
Call Graph
Dependency Graph

ممکن است دارای cycle باشند.

شناسایی SCCها کمک می‌کند بخش‌هایی از برنامه را که به شکل چرخه‌ای به یکدیگر وابسته هستند پیدا کنیم.

6. سیستم‌های Package Management

فرض کنید وابستگی پکیج‌ها چنین باشد:

Code

Package A → Package B
Package B → Package C
Package C → Package A

این ساختار یک dependency cycle ایجاد می‌کند.

چرا نمی‌توان فقط از DFS معمولی استفاده کرد؟

ممکن است این سؤال مطرح شود که اگر DFS می‌تواند گراف را پیمایش کند، چرا مستقیماً با DFS گروه‌ها را پیدا نکنیم؟

مشکل اینجاست که در گراف جهت‌دار، Reachability یک‌طرفه به معنی Strong Connectivity نیست.

اگر داشته باشیم:

Code

A → B → C

DFS از A می‌تواند هر سه گره را مشاهده کند.

اما این به معنی SCC بودن آن‌ها نیست.

زیرا از C نمی‌توان به B یا A برگشت.

پس:

Code

Reachable ≠ Strongly Connected

Kosaraju با یک تکنیک هوشمندانه این مشکل را حل می‌کند.

ایده اصلی Kosaraju چیست؟

در این مقاله وارد جزئیات اجرای الگوریتم نمی‌شویم، اما ایده اصلی را می‌توان در سه مرحله خلاصه کرد.

مرحله اول: اجرای DFS

ابتدا DFS روی گراف اصلی اجرا می‌شود و ترتیب پایان پردازش گره‌ها ثبت می‌شود.

مرحله دوم: برعکس کردن جهت تمام یال‌ها

گراف جدیدی می‌سازیم که به آن Transpose Graph گفته می‌شود.

اگر در گراف اصلی داشته باشیم:

Code

A → B

در گراف Transpose خواهیم داشت:

Code

A ← B

مرحله سوم: اجرای دوباره DFS

هر پیمایش DFS در این مرحله یک SCC را مشخص می‌کند.

به صورت خلاصه:

Code

Original Graph
      ↓
     DFS
      ↓
Finish Order
      ↓
Transpose Graph
      ↓
     DFS
      ↓
     SCCs

دلیل ریاضی اینکه چرا این روش کار می‌کند را در مقاله‌های بعدی این مجموعه بررسی خواهیم کرد.

یک مثال بسیار ساده

گراف زیر را در نظر بگیرید:

Code

A → B → C
↑       ↓
└───────┘

C → D
D → E
E → D

در بخش اول:

Code

A → B → C → A

داریم، پس:

Code

{A, B, C}

یک SCC است.

همچنین:

Code

D → E
E → D

بنابراین:

Code

{D, E}

SCC دیگری است.

هرچند از C می‌توان به D رفت، اما از D یا E نمی‌توان به A، B یا C بازگشت.

پس این دو مجموعه نباید با یکدیگر ادغام شوند.

خروجی Kosaraju برای این گراف خواهد بود:

Code

SCC 1 = {A, B, C}
SCC 2 = {D, E}

پیچیدگی زمانی Kosaraju چقدر است؟

یکی از دلایل مهم کاربردی بودن Kosaraju، کارایی بالای آن است.

با استفاده از Adjacency List، پیچیدگی زمانی الگوریتم برابر است با:

Code

O(V + E)

که در آن:

V تعداد Vertexها یا رأس‌هاست.
E تعداد Edgeها یا یال‌هاست.

یعنی الگوریتم در مقیاس گراف تقریباً خطی عمل می‌کند.

این موضوع باعث می‌شود برای گراف‌های بزرگ نیز گزینه مناسبی باشد.

آیا Kosaraju تنها الگوریتم پیدا کردن SCC است؟

خیر.

الگوریتم‌های معروف دیگری نیز برای پیدا کردن Strongly Connected Components وجود دارند، از جمله:

Tarjan's Algorithm
Gabow's Algorithm

Tarjan نیز دارای پیچیدگی زمانی O(V + E) است و می‌تواند SCCها را با یک DFS اصلی پیدا کند.

Kosaraju معمولاً به دلیل ساختار ساده و قابل فهم خود یکی از بهترین الگوریتم‌ها برای یادگیری مفهوم SCC است.

Kosaraju را چه زمانی باید به خاطر بیاوریم؟

هر زمان مسئله‌ای شامل یک Directed Graph بود و عباراتی مانند موارد زیر مشاهده کردید، احتمالاً باید به SCC فکر کنید:

گروه‌هایی از گره‌ها که همه به یکدیگر دسترسی دارند
Circular Dependency
Mutual Reachability
Cycles between modules
Groups of mutually reachable services
Strong Connectivity
Component decomposition of a directed graph

در چنین شرایطی، Kosaraju یکی از گزینه‌های اصلی حل مسئله است.

تفاوت Cycle و SCC چیست؟

این دو مفهوم مرتبط هستند اما دقیقاً یکسان نیستند.

Cycle یک مسیر بسته است:

Code

A → B → C → A

اما SCC یک مجموعه maximal از گره‌های mutually reachable است.

ممکن است داخل یک SCC چندین cycle مختلف وجود داشته باشد.

بنابراین SCC مفهومی گسترده‌تر از پیدا کردن یک cycle ساده است.

برای یادگیری Kosaraju چه چیزهایی باید بلد باشیم؟

برای فهم کامل این الگوریتم بهتر است با مفاهیم زیر آشنا باشید:

Graph و Directed Graph
Vertex و Edge
Path و Reachability
Depth-First Search یا DFS
Finish Time در DFS
Graph Transpose
Strongly Connected Components

در مقاله‌های بعدی این مجموعه، این مفاهیم را مرحله‌به‌مرحله بررسی خواهیم کرد.

جمع‌بندی

الگوریتم Kosaraju برای پیدا کردن Strongly Connected Components در یک گراف جهت‌دار طراحی شده است.

یک SCC گروهی از گره‌هاست که هر عضو آن می‌تواند از طریق مسیرهای جهت‌دار به تمام اعضای دیگر گروه برسد.

ایده کلی Kosaraju شامل دو DFS و ساخت Transpose Graph است و با استفاده از Adjacency List در زمان O(V + E) اجرا می‌شود.

اما مهم‌ترین نکته این مقاله این است:

Kosaraju فقط یک الگوریتم برای پیدا کردن cycle نیست؛ بلکه ابزاری برای کشف ساختار داخلی یک گراف جهت‌دار و تقسیم آن به مجموعه‌هایی از گره‌های mutually reachable است.

مقاله قبلی

Longest Common Substring چیست؟ پیدا کردن طولانی‌ترین بخش مشترک دو رشته با Dynamic Programming

مقاله بعدی