Connected Components یکی از مهم‌ترین مفاهیم پایه در نظریه‌ی گراف است و به ما می‌گوید یک گراف بدون‌جهت از چند بخش مستقل تشکیل شده است.

ایده ساده است:

اگر بین دو رأس مسیری وجود داشته باشد، آن دو رأس در یک Connected Component قرار دارند.

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

این مفهوم در بسیاری از مسائل واقعی دیده می‌شود:

• گروه‌های مستقل کاربران در شبکه اجتماعی
• Island Detection در Grid
• بخش‌های جداشده‌ی یک شبکه
• تشخیص زیرشبکه‌های مستقل
• Connected Regions در تصویر
• Clusterهای ارتباطی
• تحلیل ارتباط دستگاه‌ها
• تشخیص disconnected بودن یک سیستم

در این مقاله Connected Components را از پایه بررسی می‌کنیم، تفاوت آن را با Strongly Connected Components می‌فهمیم و روش‌های DFS، BFS و Union-Find را با JavaScript و TypeScript پیاده‌سازی می‌کنیم.

Connected Component دقیقاً چیست؟

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

A -- B -- C

D -- E

F

در این Graph سه بخش مستقل وجود دارد:

Component 1:
A, B, C

Component 2:
D, E

Component 3:
F

پس:

Number of Connected Components = 3

تعریف دقیق‌تر

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

1. هر دو رأس داخل مجموعه از طریق یک Path به هم می‌رسند.
2. هیچ رأس خارج از مجموعه به این Component متصل نیست.
3. مجموعه maximal است؛ یعنی نمی‌توان رأس بیشتری به آن اضافه کرد و همچنان Connected باقی ماند.

Connected Graph چیست؟

اگر کل Graph فقط یک Component داشته باشد:

components = 1

می‌گوییم Graph:

Connected

است.

اگر:

components > 1

باشد:

Disconnected Graph

داریم.

ایده‌ی اصلی پیدا کردن Componentها

الگوریتم بسیار ساده است:

1. همه Nodeها را unvisited در نظر بگیر.
2. یک Node دیده‌نشده پیدا کن.
3. از آن DFS یا BFS اجرا کن.
4. هر Nodeای که در این Traversal دیده شود متعلق به یک Component است.
5. بعد به دنبال Node دیده‌نشده‌ی بعدی بگرد.
6. هر Traversal جدید یک Component جدید می‌سازد.

چرا این روش درست است؟

وقتی DFS یا BFS را از یک Node شروع می‌کنیم، دقیقاً تمام Nodeهایی را پیدا می‌کنیم که از آن reachable هستند.

در Undirected Graph:

reachable from A

به معنی:

in the same connected component as A

است.

پس یک Traversal کامل دقیقاً یک Component را می‌سازد.

مثال مرحله‌به‌مرحله

Graph:

A -- B -- C

D -- E

F

ابتدا:

visited = {}
components = []

از A شروع می‌کنیم:

A → B → C

پس:

component1 = [A, B, C]

visited:

{A, B, C}

بعد D هنوز دیده نشده:

D → E

پس:

component2 = [D, E]

در آخر F تنهاست:

component3 = [F]

نتیجه:

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

پیاده‌سازی با DFS

function connectedComponentsDFS(graph) {
  const visited = new Set();
  const result = [];

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

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

  for (const node of Object.keys(graph)) {
    if (visited.has(node)) continue;

    const component = [];

    dfs(node, component);

    result.push(component);
  }

  return result;
}

مثال

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

console.log(
  connectedComponentsDFS(graph)
);

خروجی:

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

پیاده‌سازی Iterative DFS

اگر Graph خیلی عمیق باشد، Recursive DFS ممکن است Stack Overflow ایجاد کند.

نسخه‌ی Iterative:

function connectedComponentsIterative(graph) {
  const visited = new Set();
  const result = [];

  for (const start of Object.keys(graph)) {
    if (visited.has(start)) continue;

    const stack = [start];
    const component = [];

    visited.add(start);

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

      component.push(node);

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

        visited.add(next);
        stack.push(next);
      }
    }

    result.push(component);
  }

  return result;
}

پیاده‌سازی با BFS

DFS و BFS هر دو برای این مسئله مناسب‌اند.

function connectedComponentsBFS(graph) {
  const visited = new Set();
  const result = [];

  for (const start of Object.keys(graph)) {
    if (visited.has(start)) continue;

    const queue = [start];
    let head = 0;

    const component = [];

    visited.add(start);

    while (head < queue.length) {
      const node = queue[head++];

      component.push(node);

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

        visited.add(next);
        queue.push(next);
      }
    }

    result.push(component);
  }

  return result;
}

DFS یا BFS؟

برای پیدا کردن Connected Components از نظر پیچیدگی تقریباً یکسان‌اند.

هر دو:

O(V + E)

هستند.

انتخاب معمولاً به Style یا Requirement بستگی دارد.

DFS

مزایا:

• کد Recursive ساده
• مناسب Graph Algorithms
• طبیعی برای Structural Analysis

BFS

مزایا:

• بدون Recursion
• Level information
• مناسب وقتی distance هم مهم باشد

فقط شمارش Componentها

گاهی خود لیست Nodeها مهم نیست و فقط تعداد Componentها را می‌خواهیم.

function countComponents(graph) {
  const visited = new Set();
  let count = 0;

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

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

  for (const node of Object.keys(graph)) {
    if (visited.has(node)) continue;

    count++;
    dfs(node);
  }

  return count;
}

Component ID

در بسیاری از سیستم‌های واقعی بهتر است فقط List نداشته باشیم و برای هر Node یک Component ID ذخیره کنیم.

مثلاً:

A → component 0
B → component 0
C → component 0

D → component 1
E → component 1

F → component 2

پیاده‌سازی Component Labeling

function labelComponents(graph) {
  const componentId = new Map();

  let id = 0;

  function dfs(start) {
    const stack = [start];

    componentId.set(start, id);

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

      for (const next of graph[node] ?? []) {
        if (componentId.has(next)) continue;

        componentId.set(next, id);
        stack.push(next);
      }
    }
  }

  for (const node of Object.keys(graph)) {
    if (componentId.has(node)) continue;

    dfs(node);
    id++;
  }

  return {
    count: id,
    componentId
  };
}

این روش برای Queryهای بعدی بسیار مفید است.

مثلاً:

are A and E connected?

فقط بررسی می‌کنیم:

componentId[A] === componentId[E]

تفاوت Connected Components و Strongly Connected Components

این تفاوت بسیار مهم است.

Connected Components

معمولاً برای:

Undirected Graph

است.

اگر بین A و B Path وجود داشته باشد، چون Edgeها بدون جهت‌اند، ارتباط دوطرفه طبیعی است.

Strongly Connected Components

برای:

Directed Graph

است.

A و B زمانی در یک SCC هستند که:

A → ... → B

و:

B → ... → A

هر دو ممکن باشند.

پس:

Undirected Graph
→ Connected Components

Directed Graph
→ Strongly Connected Components

Weakly Connected Components چیست؟

در Directed Graph یک مفهوم دیگر داریم:

Weakly Connected Component

یعنی Direction یال‌ها را موقتاً Ignore کنیم و Componentها را روی نسخه Undirected پیدا کنیم.

مثلاً:

A → B → C

از نظر Strong Connectivity شاید همه در یک SCC نباشند.

اما اگر Direction را Ignore کنیم:

A -- B -- C

یک Weakly Connected Component داریم.

Connected Components و Union-Find

اگر Graph به صورت Edge List داده شده باشد یا Edgeها به‌مرور اضافه شوند، Union-Find / DSU بسیار مفید است.

ایده:

ابتدا هر Node Component خودش است.

A
B
C
D

اگر Edge:

A -- B

اضافه شود:

{A, B}
{C}
{D}

بعد:

B -- C

داریم:

{A, B, C}
{D}

پیاده‌سازی DSU

class DSU {
  constructor(nodes) {
    this.parent = new Map();
    this.rank = new Map();

    for (const node of nodes) {
      this.parent.set(node, node);
      this.rank.set(node, 0);
    }
  }

  find(x) {
    if (this.parent.get(x) !== x) {
      this.parent.set(
        x,
        this.find(this.parent.get(x))
      );
    }

    return this.parent.get(x);
  }

  union(a, b) {
    let rootA = this.find(a);
    let rootB = this.find(b);

    if (rootA === rootB) {
      return false;
    }

    const rankA = this.rank.get(rootA);
    const rankB = this.rank.get(rootB);

    if (rankA < rankB) {
      [rootA, rootB] = [rootB, rootA];
    }

    this.parent.set(rootB, rootA);

    if (rankA === rankB) {
      this.rank.set(rootA, rankA + 1);
    }

    return true;
  }
}

شمارش Componentها با DSU

function countComponentsDSU(nodes, edges) {
  const dsu = new DSU(nodes);

  let count = nodes.length;

  for (const [u, v] of edges) {
    if (dsu.union(u, v)) {
      count--;
    }
  }

  return count;
}

ایده مهم:

هر بار دو Component متفاوت را Union می‌کنیم:

componentCount--

DFS/BFS یا Union-Find؟

DFS/BFS

مناسب وقتی:

• Graph کامل از قبل داریم.
• Adjacency List داریم.
• می‌خواهیم اعضای هر Component را استخراج کنیم.

Union-Find

مناسب وقتی:

• Edgeها Stream می‌شوند.
• Dynamic Connectivity داریم.
• Queryهای زیادی مثل connected(a,b) داریم.
• الگوریتم‌هایی مثل Kruskal اجرا می‌کنیم.

Dynamic Connectivity

فرض کنید شبکه‌ای داریم و Connectionها به‌مرور اضافه می‌شوند.

Query:

آیا Device A و Device Z در یک شبکه هستند؟

با DSU:

dsu.find("A") === dsu.find("Z")

را بررسی می‌کنیم.

این یکی از کاربردهای مهم Union-Find است.

Island Detection

یکی از مشهورترین کاربردهای Connected Components، مسئله‌ی Number of Islands است.

Grid:

1 1 0 0
1 0 0 1
0 0 1 1

اگر:

1 = land
0 = water

باشد، هر مجموعه‌ی متصل از Cellهای 1 یک Component یا Island است.

Number of Islands با DFS

function numIslands(grid) {
  const rows = grid.length;
  const cols = grid[0].length;

  let count = 0;

  function dfs(r, c) {
    if (
      r < 0 ||
      r >= rows ||
      c < 0 ||
      c >= cols
    ) {
      return;
    }

    if (grid[r][c] !== "1") {
      return;
    }

    grid[r][c] = "0";

    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === "1") {
        count++;
        dfs(r, c);
      }
    }
  }

  return count;
}

این در اصل Connected Components روی Grid است.

4-direction یا 8-direction

در Grid باید تعریف Connected بودن را دقیق مشخص کنیم.

4-direction

up
down
left
right

8-direction

علاوه بر آن:

diagonals

هم Connected محسوب می‌شوند.

این انتخاب می‌تواند تعداد Componentها را تغییر دهد.

Connected Regions در Image Processing

در پردازش تصویر، Pixelهای مشابه را می‌توان Node فرض کرد.

Adjacent Pixelها Edge هستند.

Connected Components برای:

• Object Detection اولیه
• Blob Detection
• Region Labeling
• Character Segmentation
• Medical Image Region Analysis

استفاده می‌شود.

این حوزه معمولاً با نام:

Connected Component Labeling

شناخته می‌شود.

Social Network

فرض کنید:

User = Vertex
Friendship = Edge

اگر دو گروه هیچ ارتباطی با هم نداشته باشند، دو Component جدا داریم.

مثلاً:

Group A:
Alice, Bob, Carol

Group B:
David, Eve

Connected Components می‌تواند گروه‌های کاملاً جدا را پیدا کند.

Computer Network

فرض کنید:

Device = Vertex
Physical Link = Edge

اگر بخشی از شبکه از بقیه جدا شود، Graph چند Component می‌شود.

کاربرد:

• Network partition detection
• Fault isolation
• Infrastructure analysis

Wireless Networks

در شبکه‌های بی‌سیم:

Device A connected to B
if distance <= range

می‌توان Connectivity Graph ساخت.

Connected Components نشان می‌دهد چند گروه از Deviceها می‌توانند غیرمستقیم با هم ارتباط داشته باشند.

Road Network

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

Connected Components نشان می‌دهد کدام شهرها هنوز به هم دسترسی دارند.

البته اگر Direction خیابان مهم باشد، باید مدل Directed مناسب‌تری استفاده شود.

Clusterهای کاربران

گاهی Edge نشان‌دهنده‌ی interaction است:

User A interacted with User B

Connected Components می‌تواند گروه‌های جدا از Interaction Network را پیدا کند.

اما باید دقت کنیم:

Connected Component ≠ Community Detection

تفاوت Connected Components با Community Detection

Connected Component فقط می‌گوید:

آیا بین دو Node مسیری وجود دارد؟

اما Community Detection می‌خواهد گروه‌هایی با ارتباط داخلی قوی‌تر پیدا کند، حتی اگر کل Graph Connected باشد.

مثلاً ممکن است کل Social Network فقط یک Component باشد ولی صدها Community داشته باشد.

Connected Components و Clustering

این مفاهیم مشابه به نظر می‌رسند ولی یکسان نیستند.

Connected Components بر اساس Graph Connectivity دقیق عمل می‌کند.

Clustering معمولاً بر اساس:

• distance
• similarity
• density
• statistical structure

است.

اندازه Componentها

گاهی مهم است بدانیم بزرگ‌ترین Component کدام است.

function largestComponentSize(graph) {
  const visited = new Set();
  let best = 0;

  for (const start of Object.keys(graph)) {
    if (visited.has(start)) continue;

    const stack = [start];
    visited.add(start);

    let size = 0;

    while (stack.length > 0) {
      const node = stack.pop();
      size++;

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

        visited.add(next);
        stack.push(next);
      }
    }

    best = Math.max(best, size);
  }

  return best;
}

Giant Component

در Network Science گاهی یک Component بسیار بزرگ داریم که بخش عمده Nodeها را شامل می‌شود.

به آن معمولاً:

Giant Connected Component

می‌گویند.

در تحلیل شبکه‌های اجتماعی و زیرساختی مفهوم مهمی است.

آیا دو Node Connected هستند؟

اگر فقط یک Query داریم:

A connected to B?

می‌توانیم DFS/BFS از A اجرا کنیم و ببینیم B قابل دسترس است یا نه.

اگر Queryهای زیادی داریم، Component ID یا DSU بهتر است.

Preprocessing برای Queryهای زیاد

اگر Graph static است:

1. Componentها را یک بار پیدا کن.
2. به هر Node componentId بده.
3. هر Query را در O(1) جواب بده.

same component?
componentId[a] === componentId[b]

Edge Cases

Graph خالی

V = 0

تعداد Componentها:

0

یک Node تنها

A

یک Component داریم.

همه Nodeها ایزوله

A   B   C   D

هر Node Component مستقل است.

پس:

components = V

Graph کامل Connected

اگر همه Nodeها به هم متصل باشند:

components = 1

Duplicate Edge

وجود Edge تکراری نباید Component جدید ایجاد کند.

Self-loop

A -- A

Node را به Component دیگری متصل نمی‌کند؛ فقط یک Loop داخلی است.

پیچیدگی DFS/BFS

با adjacency list:

Time = O(V + E)

چون هر Vertex و Edge تعداد محدودی بررسی می‌شود.

فضای کمکی:

O(V)

برای:

• visited
• stack / queue
• component labels

Complexity با Adjacency Matrix

اگر Graph با Matrix ذخیره شود، برای هر Node باید Row کامل بررسی شود.

پس:

O(V²)

ممکن است لازم باشد.

Complexity Union-Find

با Path Compression و Union by Rank:

find / union
≈ O(α(V))

در عمل تقریباً ثابت است.

برای کل Edgeها:

O(E α(V))

TypeScript Version

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

function connectedComponents(
  graph: Graph
): string[][] {
  const visited = new Set<string>();
  const result: string[][] = [];

  function dfs(
    node: string,
    component: string[]
  ): void {
    visited.add(node);
    component.push(node);

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

  for (const node of Object.keys(graph)) {
    if (visited.has(node)) continue;

    const component: string[] = [];

    dfs(node, component);

    result.push(component);
  }

  return result;
}

خطاهای رایج

1. فقط یک DFS اجرا کردن

اگر Graph disconnected باشد، فقط Component نقطه شروع پیدا می‌شود.

باید روی همه Nodeهای unvisited loop کنیم.

2. فراموش کردن Nodeهای ایزوله

اگر Node در Object وجود داشته باشد ولی adjacency list خالی باشد:

F: []

خودش یک Component است.

3. استفاده از Connected Components برای Directed Graph

در Directed Graph باید دقیق کنیم منظور:

• Weakly Connected
• Strongly Connected

است.

4. اشتباه گرفتن Component با Cluster

هر Connected Component الزاماً یک Community معنایی نیست.

5. تغییر Grid در-place بدون توجه

در Number of Islands تغییر:

1 → 0

سریع است، ولی Input را تغییر می‌دهد.

اگر Input باید حفظ شود، visited جدا لازم است.

6. Recursion عمیق

در Graphهای بزرگ Recursive DFS ممکن است Stack Overflow بدهد.

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

وقتی:

• Graph بدون‌جهت داریم.
• می‌خواهیم بخش‌های مستقل را پیدا کنیم.
• Network Partition مهم است.
• Island Detection داریم.
• Connected Regions می‌خواهیم.
• Component Count لازم داریم.
• Connectivity Query داریم.
• گروه‌های disconnected را تحلیل می‌کنیم.

چه زمانی مناسب نیست؟

اگر Graph جهت‌دار است و Mutual Reachability مهم است:

Strongly Connected Components

مناسب‌تر است.

اگر فقط Shortest Path می‌خواهید:

BFS / Dijkstra

بسته به Weight.

اگر Community ساختاری می‌خواهید:

Community Detection

مفهوم مناسب‌تری است.

جدول تصمیم سریع

جمع‌بندی

Connected Components یکی از ساده‌ترین اما مهم‌ترین Patternهای Graph Algorithm است.

الگوی اصلی:

for each unvisited node:
    run DFS/BFS
    one traversal = one component

با adjacency list پیچیدگی:

O(V + E)

است.

اگر Edgeها به‌مرور اضافه شوند یا Queryهای Connectivity زیادی داشته باشیم، Union-Find انتخاب بسیار خوبی است.

اما مهم‌ترین نکته این است که قبل از انتخاب الگوریتم، نوع Connectivity را مشخص کنیم:

Undirected Graph
→ Connected Components

Directed Graph + ignore direction
→ Weakly Connected Components

Directed Graph + mutual reachability
→ Strongly Connected Components

Pattern مسئله نیز ساده است:

آیا Graph به چند جزیره‌ی مستقل تقسیم شده؟
آیا دو Node در یک گروه ارتباطی هستند؟
آیا بخشی از Network از بقیه جدا شده؟
آیا Grid چند Region مستقل دارد؟

→ Connected Components