Strongly Connected Components یا SCC یکی از مهم‌ترین مفاهیم در گراف‌های جهت‌دار است. ایده‌ی اصلی آن ساده است: می‌خواهیم رأس‌های یک گراف جهت‌دار را به گروه‌هایی تقسیم کنیم که داخل هر گروه، از هر رأس بتوان به تمام رأس‌های دیگر همان گروه رسید.

به بیان دقیق‌تر، اگر دو رأس u و v داخل یک SCC باشند، باید هم مسیری از u به v وجود داشته باشد و هم مسیری از v به u.

این تفاوت کوچک اما مهم، SCC را از Connected Components در گراف بدون‌جهت جدا می‌کند.

قبل از SCC: Reachability یعنی چه؟

فرض کنید یال A -> B داریم. این یعنی از A می‌توان مستقیماً به B رفت. اگر مسیر زیر را داشته باشیم:

A -> B -> C

می‌گوییم C از A قابل دسترسی یا Reachable است.

اما برای strongly connected بودن A و C کافی نیست که فقط A به C برسد. باید C هم بتواند دوباره به A برگردد.

مثلاً:

A -> B
^    |
|    v
C <- D

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

تعریف رسمی SCC

در یک گراف جهت‌دار G = (V, E)، یک Strongly Connected Component زیرمجموعه‌ای بیشینه از رأس‌هاست که برای هر دو رأس u و v در آن:

u ~> v
v ~> u

وجود داشته باشد.

کلمه‌ی بیشینه مهم است. یعنی اگر بتوان رأس دیگری را به این مجموعه اضافه کرد و همچنان خاصیت دسترسی دوطرفه حفظ شود، مجموعه‌ی قبلی SCC کامل نبوده است.

یک مثال ساده

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

A -> B -> C
^    |    |
|    v    v
D <- E    F -> G
     ^         |
     |_________|

ممکن است پس از بررسی مسیرها به گروه‌هایی مانند این برسیم:

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

نکته این است که وجود مسیر یک‌طرفه بین دو گروه باعث ادغام آن‌ها نمی‌شود. برای قرارگرفتن در یک SCC، ارتباط باید از نظر reachability دوطرفه باشد.

چرا SCC مهم است؟

SCC فقط یک مسئله‌ی دانشگاهی نیست. در بسیاری از سیستم‌های واقعی لازم است بفهمیم کدام موجودیت‌ها وابستگی چرخه‌ای و برگشت‌پذیر دارند.

نمونه‌ها:

• تشخیص Circular Dependency بین ماژول‌ها
• تحلیل dependency graph در package managerها
• پیدا کردن چرخه‌های وابستگی بین microserviceها
• تحلیل شبکه‌های اجتماعی با ارتباط جهت‌دار
• بررسی workflowهایی که امکان برگشت به حالت قبلی دارند
• تحلیل state machineها
• ساده‌سازی گراف‌های بزرگ برای پردازش‌های بعدی
• تحلیل call graph و control-flow graph
• بررسی لینک‌های بین صفحات وب یا اسناد
• تحلیل dependency بین taskها و jobها

دو الگوریتم معروف SCC

دو روش کلاسیک برای پیدا کردن SCCها عبارت‌اند از:

1. Kosaraju's Algorithm
2. Tarjan's Algorithm

هر دو در زمان خطی اجرا می‌شوند:

O(V + E)

اما ایده‌ی آن‌ها متفاوت است.

Kosaraju معمولاً برای یادگیری ساده‌تر است، چون از دو DFS و یک گراف معکوس استفاده می‌کند.

Tarjan تنها با یک DFS و مفهوم low-link کار می‌کند، اما درک آن کمی پیچیده‌تر است.

در این مقاله Kosaraju را مبنا قرار می‌دهیم.

الگوریتم Kosaraju چگونه کار می‌کند؟

Kosaraju سه مرحله‌ی اصلی دارد:

1. اجرای DFS روی گراف اصلی و ثبت ترتیب پایان رأس‌ها
2. معکوس کردن تمام یال‌های گراف
3. اجرای DFS روی گراف معکوس با ترتیب معکوس زمان پایان

هر DFS در مرحله‌ی سوم دقیقاً یک SCC تولید می‌کند.

مرحله اول: Finishing Order

در DFS فقط مهم نیست چه زمانی وارد یک رأس می‌شویم؛ زمان تمام‌شدن پردازش آن هم مهم است.

فرض کنید:

A -> B -> C

DFS از A شروع می‌شود:

enter A
enter B
enter C
finish C
finish B
finish A

بنابراین ترتیب پایان:

C, B, A

است.

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

مرحله دوم: Reverse Graph

در گراف معکوس، جهت تمام یال‌ها برعکس می‌شود.

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

A -> B
B -> C
C -> A
C -> D

در گراف معکوس داریم:

B -> A
C -> B
A -> C
D -> C

نکته‌ی مهم این است که معکوس‌کردن یال‌ها اعضای هر SCC را تغییر نمی‌دهد؛ اگر دو رأس در گراف اصلی بتوانند به یکدیگر برسند، در گراف معکوس نیز همچنان mutual reachability دارند.

مرحله سوم: DFS روی گراف معکوس

حالا رأس‌ها را از بیشترین finishing time به کمترین پردازش می‌کنیم.

هر بار که به یک رأس visit نشده می‌رسیم، یک DFS جدید آغاز می‌کنیم. تمام رأس‌هایی که در همان DFS پیدا می‌شوند، یک SCC هستند.

شهود اینکه چرا Kosaraju کار می‌کند

اگر هر SCC را به یک super-node تبدیل کنیم، گراف جدید دیگر هیچ چرخه‌ای ندارد و یک DAG می‌شود. به این گراف Condensation Graph می‌گویند.

DFS اول عملاً به ما ترتیبی می‌دهد که بتوانیم SCCهای مناسب را از انتهای این DAG شروع کنیم. وقتی یال‌ها را معکوس می‌کنیم، جهت ارتباط بین SCCها نیز برمی‌گردد و DFS مرحله‌ی دوم نمی‌تواند ناخواسته وارد SCCای شود که نباید عضو گروه فعلی باشد.

این همان ایده‌ای است که باعث می‌شود هر DFS مرحله‌ی دوم دقیقاً یک SCC را استخراج کند.

پیاده‌سازی کامل JavaScript

function kosaraju(graph) {
  const visited = new Set();
  const finishOrder = [];

  function dfs1(node) {
    visited.add(node);

    for (const neighbor of graph[node] ?? []) {
      if (!visited.has(neighbor)) {
        dfs1(neighbor);
      }
    }

    finishOrder.push(node);
  }

  const allNodes = new Set(Object.keys(graph));

  for (const neighbors of Object.values(graph)) {
    for (const node of neighbors) {
      allNodes.add(node);
    }
  }

  for (const node of allNodes) {
    if (!visited.has(node)) {
      dfs1(node);
    }
  }

  const reversed = {};

  for (const node of allNodes) {
    reversed[node] = [];
  }

  for (const [from, neighbors] of Object.entries(graph)) {
    for (const to of neighbors) {
      reversed[to].push(from);
    }
  }

  visited.clear();

  const components = [];

  function dfs2(node, component) {
    visited.add(node);
    component.push(node);

    for (const neighbor of reversed[node] ?? []) {
      if (!visited.has(neighbor)) {
        dfs2(neighbor, component);
      }
    }
  }

  while (finishOrder.length > 0) {
    const node = finishOrder.pop();

    if (!visited.has(node)) {
      const component = [];
      dfs2(node, component);
      components.push(component);
    }
  }

  return components;
}

const graph = {
  A: ["B"],
  B: ["C", "E"],
  C: ["A", "D"],
  D: ["E"],
  E: ["D"],
  F: ["E", "G"],
  G: ["F"]
};

console.log(kosaraju(graph));

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

[
  ["F", "G"],
  ["A", "B", "C"],
  ["D", "E"]
]

پیاده‌سازی TypeScript

type Graph = Record<string, string[]>;

function stronglyConnectedComponents(graph: Graph): string[][] {
  const nodes = new Set<string>(Object.keys(graph));

  for (const neighbors of Object.values(graph)) {
    neighbors.forEach((node) => nodes.add(node));
  }

  const visited = new Set<string>();
  const order: string[] = [];

  const dfsOrder = (node: string): void => {
    visited.add(node);

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) dfsOrder(next);
    }

    order.push(node);
  };

  nodes.forEach((node) => {
    if (!visited.has(node)) dfsOrder(node);
  });

  const reversed: Graph = {};

  nodes.forEach((node) => {
    reversed[node] = [];
  });

  for (const [from, neighbors] of Object.entries(graph)) {
    for (const to of neighbors) {
      reversed[to].push(from);
    }
  }

  visited.clear();

  const result: string[][] = [];

  const collect = (node: string, component: string[]): void => {
    visited.add(node);
    component.push(node);

    for (const next of reversed[node] ?? []) {
      if (!visited.has(next)) collect(next, component);
    }
  };

  while (order.length) {
    const node = order.pop()!;

    if (!visited.has(node)) {
      const component: string[] = [];
      collect(node, component);
      result.push(component);
    }
  }

  return result;
}

Condensation Graph چیست؟

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

فرض کنید SCCها این‌ها باشند:

S1 = {A, B, C}
S2 = {D, E}
S3 = {F}

هر SCC را به یک node تبدیل می‌کنیم:

S1 -> S2 -> S3

این گراف جدید همیشه یک Directed Acyclic Graph یا DAG است.

چرا؟ چون اگر بین SCCهای فشرده‌شده چرخه وجود داشت، آن SCCها در واقع قابل ادغام در یک SCC بزرگ‌تر بودند.

این خاصیت در طراحی compiler، dependency analysis، scheduling و graph optimization بسیار مفید است.

کاربردهای واقعی‌تر

1. Circular Dependency در پروژه‌های نرم‌افزاری

فرض کنید:

Auth -> User
User -> Payment
Payment -> Auth

این سه ماژول یک چرخه‌ی dependency ساخته‌اند. SCC می‌تواند کل این مجموعه را به عنوان یک component شناسایی کند.

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

2. Microservices

اگر سرویس A برای انجام کارش به B وابسته باشد، B به C و C دوباره به A، یک dependency cycle داریم.

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

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

در شبکه‌ای مثل X/Twitter، follow معمولاً جهت‌دار است.

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

4. State Machine

در یک state machine، SCC می‌تواند stateهایی را پیدا کند که از داخل آن‌ها بتوان بین حالت‌ها گردش کرد و دوباره به حالت اولیه برگشت.

این موضوع برای تشخیص loopهای رفتاری مهم است.

5. Web Crawling

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

پیچیدگی زمانی

Kosaraju شامل:

• یک DFS روی گراف اصلی
• ساخت گراف معکوس
• یک DFS روی گراف معکوس

است.

هر رأس و هر یال فقط تعداد ثابتی بار پردازش می‌شود، پس:

Time Complexity: O(V + E)

و به دلیل نگهداری گراف معکوس، visited، stack/order و خروجی:

Space Complexity: O(V + E)

است.

Edge Caseهای مهم

رأس بدون یال

A

به تنهایی یک SCC است.

Self-loop

A -> A

A همچنان یک SCC تک‌رأسی است.

گراف کاملاً strongly connected

اگر همه‌ی رأس‌ها بتوانند به یکدیگر برسند، کل گراف فقط یک SCC دارد.

DAG

اگر گراف جهت‌دار هیچ چرخه‌ای نداشته باشد، هر رأس به تنهایی یک SCC است.

این نکته در مصاحبه‌ها بسیار مهم است.

تفاوت SCC با Connected Components

در گراف بدون‌جهت:

A -- B -- C

اگر بین دو رأس مسیر وجود داشته باشد، اتصال ذاتاً دوطرفه است.

اما در گراف جهت‌دار:

A -> B

A به B می‌رسد، ولی لزوماً B به A نمی‌رسد.

پس برای گراف جهت‌دار، Connected Component معمولی مفهوم کافی‌ای نیست و Strong Connectivity مطرح می‌شود.

SCC و Cycle چه تفاوتی دارند؟

هر SCC با بیش از یک رأس حتماً شامل حداقل یک cycle است، اما SCC فقط «پیدا کردن یک چرخه» نیست.

SCC می‌خواهد کل مجموعه‌ی بیشینه‌ای را پیدا کند که همه‌ی اعضایش از نظر reachability دوطرفه به هم متصل باشند.

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

Kosaraju یا Tarjan؟

Kosaraju

مزایا:

• ساده‌تر برای یادگیری
• ایده‌ی واضح
• پیاده‌سازی مستقیم

معایب:

• نیاز به دو DFS
• نیاز به ساخت گراف معکوس

Tarjan

مزایا:

• فقط یک DFS
• نیازی به reverse graph ندارد

معایب:

• درک index، low-link و stack کمی دشوارتر است

هر دو:

O(V + E)

هستند.

اشتباهات رایج

• استفاده از BFS/DFS ساده و تصور اینکه یک component معمولی همان SCC است
• فراموش‌کردن جهت یال‌ها
• پردازش رأس‌هایی که فقط در لیست همسایه‌ها ظاهر شده‌اند
• اشتباه در ترتیب finishing time
• اجرای DFS دوم روی گراف اصلی به جای reversed graph
• مخلوط‌کردن مفهوم SCC با cycle detection
• تصور اینکه ترتیب SCCهای خروجی باید همیشه ثابت باشد

چه زمانی از SCC استفاده کنیم؟

وقتی مسئله شامل یک گراف جهت‌دار است و سؤال شبیه یکی از این‌هاست:

• کدام رأس‌ها به صورت رفت‌وبرگشتی به هم دسترسی دارند؟
• کدام dependencyها چرخه‌ای‌اند؟
• کدام بخش‌های سیستم tightly coupled هستند؟
• چگونه یک directed graph را به DAG تبدیل کنیم؟
• کدام stateها می‌توانند به یکدیگر برگردند؟
• کدام سرویس‌ها یا ماژول‌ها در یک dependency cycle قرار دارند؟

در چنین مسائلی SCC معمولاً ابزار بسیار مناسبی است.

جمع‌بندی

Strongly Connected Components یکی از پایه‌ای‌ترین ابزارها برای تحلیل گراف‌های جهت‌دار است.

ایده‌ی اصلی آن این است:

رأس‌هایی را در یک گروه قرار بده که هر کدام بتواند به دیگری برسد و مسیر برگشت نیز وجود داشته باشد.

Kosaraju این مسئله را با سه ایده حل می‌کند:

DFS finishing order
        ↓
Reverse Graph
        ↓
DFS in reverse finishing order
        ↓
SCCs

در سطح مهندسی نرم‌افزار، SCC را می‌توان برای dependency analysis، شناسایی circular dependency، تحلیل microserviceها، state machineها، شبکه‌های اجتماعی و ساده‌سازی گراف‌های پیچیده استفاده کرد.

اگر مفهوم mutual reachability، finishing time و condensation graph را خوب بفهمید، SCC دیگر یک الگوریتم حفظ‌کردنی نخواهد بود؛ بلکه به ابزاری قابل‌استفاده برای مدل‌سازی و حل مسائل واقعی تبدیل می‌شود.