Bridge یا Cut Edge یالی در یک گراف بدون‌جهت است که اگر حذف شود، تعداد Connected Componentهای گراف افزایش پیدا می‌کند.

به زبان ساده:

Bridge یک ارتباط حیاتی است که اگر قطع شود، بخشی از شبکه از بخش دیگر جدا می‌شود.

این مفهوم در Network Reliability، طراحی زیرساخت، شبکه‌های ارتباطی، دیتاسنتر، حمل‌ونقل، سیستم‌های توزیع‌شده و تحلیل Redundancy بسیار مهم است.

در این مقاله از تعریف ساده شروع می‌کنیم، تفاوت Bridge با Articulation Point را می‌بینیم، مفهوم discovery time و low-link را یاد می‌گیریم و الگوریتم Tarjan را با JavaScript و TypeScript پیاده‌سازی می‌کنیم.

یک مثال ساده

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

Code

A -- B -- C
     |
     D

یال:

Code

A -- B

Bridge است.

چرا؟

اگر آن را حذف کنیم:

Code

A

B -- C
|
D

رأس A از بقیه Graph جدا می‌شود.

همین‌طور:

Code

B -- C

و:

Code

B -- D

نیز Bridge هستند.

تعریف دقیق

در یک Graph بدون‌جهت:

Code

G = (V, E)

یال:

Code

e = (u, v)

یک Bridge است اگر:

Code

components(G - e)
>
components(G)

یعنی حذف آن تعداد Componentها را بیشتر کند.

چرا Bridge مهم است؟

فرض کنید Graph نماینده‌ی یک شبکه واقعی باشد:

Code

Data Center = Vertex
Network Link = Edge

اگر فقط یک Link بین دو Zone وجود داشته باشد، قطع آن Link باعث Partition شدن شبکه می‌شود.

پس آن Link:

Code

Single Point of Failure

در سطح Edge است.

تفاوت Bridge با Articulation Point

Bridge

یک Edge بحرانی است.

Code

remove edge
→ connectivity decreases

Articulation Point

یک Vertex بحرانی است.

Code

remove vertex
→ connectivity decreases

پس:

Code

Bridge = critical edge
Articulation Point = critical vertex

روش ساده Brute Force

یک راه ساده برای پیدا کردن Bridgeها:

برای هر Edge:

Edge را موقتاً حذف کن.
تعداد Connected Componentها را حساب کن.
Edge را برگردان.
اگر Componentها بیشتر شدند، Edge یک Bridge است.

مشکل Brute Force

اگر E یال داشته باشیم و برای هر یال DFS/BFS کامل اجرا کنیم:

Code

O(E × (V + E))

می‌شود.

برای Graph بزرگ مناسب نیست.

روش بهینه: Tarjan + DFS

می‌توان همه Bridgeها را با یک DFS پیدا کرد.

Complexity:

Code

O(V + E)

مفاهیم اصلی:

Code

disc[u]
low[u]

هستند.

discovery time چیست؟

disc[u] زمان اولین Visit شدن رأس u در DFS است.

مثلاً:

Code

A → B → C → D

ممکن است:

Code

disc[A] = 1
disc[B] = 2
disc[C] = 3
disc[D] = 4

باشد.

low-link value چیست؟

low[u] کوچک‌ترین discovery time رأسی است که از Subtree مربوط به u می‌توان از طریق:

Tree Edgeهای DFS
و Back Edge

به آن رسید.

به زبان شهودی:

low نشان می‌دهد Subtree این Node چقدر می‌تواند به Ancestorهای قبلی یک مسیر جایگزین داشته باشد.

مثال برای low

فرض کنید:

Code

A
|
B
|
C
|
D

و Edge:

Code

D -- A

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

پس از D می‌توان مستقیم به A برگشت.

بنابراین:

Code

low[D] = disc[A]

و این مقدار به بالا منتقل می‌شود.

شرط Bridge

فرض کنید در DFS:

Code

u
|
v

و (u, v) یک Tree Edge باشد.

اگر:

Code

low[v] > disc[u]

آنگاه:

Code

(u, v) = Bridge

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

اگر:

Code

low[v] > disc[u]

باشد، یعنی Subtree مربوط به v هیچ Back Edgeای به u یا Ancestorهای u ندارد.

پس تنها راه اتصال آن Subtree به بخش بالای Graph همین Edge:

Code

u -- v

است.

اگر این Edge حذف شود، Subtree جدا می‌شود.

چرا شرط > است؟

این تفاوت را با Articulation Point باید دقیق یاد بگیریم.

برای Bridge:

Code

low[v] > disc[u]

برای Articulation Point غیرریشه:

Code

low[v] >= disc[u]

چرا؟

اگر:

Code

low[v] = disc[u]

باشد، Subtree می‌تواند با Back Edge به خود u برگردد.

در این حالت Edge (u,v) تنها راه اتصال نیست، پس Bridge نیست.

اما اگر خود u حذف شود، آن Back Edge هم از بین می‌رود؛ بنابراین u ممکن است Articulation Point باشد.

Tree Edge و Back Edge

در DFS دو نوع Edge مهم داریم.

Tree Edge

Edgeای که با آن برای اولین بار وارد یک Node جدید می‌شویم.

Code

u → v

که v قبلاً unvisited بوده.

Back Edge

Edgeای که از Node فعلی یا Subtree آن به Ancestor قبلی برمی‌گردد.

Back Edge نشانه‌ی وجود مسیر جایگزین است.

مثال Cycle

Graph:

Code

A -- B
|    |
D -- C

هیچ Edgeای Bridge نیست.

چرا؟

اگر هر Edge را حذف کنیم، هنوز از مسیر دیگر می‌توان بین Nodeها رفت.

مثلاً حذف:

Code

A -- B

باز هم:

Code

A → D → C → B

مسیر جایگزین است.

یک قانون مهم

در Graph بدون‌جهت:

Edgeای که روی هیچ Cycle قرار ندارد، Bridge است.

و بالعکس:

اگر Edge در یک Cycle باشد، Bridge نیست.

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

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

JavaScript

function findBridges(graph) {
  const nodes = new Set();

  for (const [u, neighbors] of Object.entries(graph)) {
    nodes.add(u);

    for (const v of neighbors) {
      nodes.add(v);
    }
  }

  const visited = new Set();
  const disc = new Map();
  const low = new Map();
  const parent = new Map();

  const bridges = [];

  let time = 0;

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

    disc.set(u, ++time);
    low.set(u, disc.get(u));

    for (const v of graph[u] ?? []) {
      if (!visited.has(v)) {
        parent.set(v, u);

        dfs(v);

        low.set(
          u,
          Math.min(
            low.get(u),
            low.get(v)
          )
        );

        if (
          low.get(v) > disc.get(u)
        ) {
          bridges.push([u, v]);
        }
      } else if (
        v !== parent.get(u)
      ) {
        low.set(
          u,
          Math.min(
            low.get(u),
            disc.get(v)
          )
        );
      }
    }
  }

  for (const node of nodes) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }

  return bridges;
}

مثال اجرا

JavaScript

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

console.log(findBridges(graph));

خروجی می‌تواند:

JSON

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

باشد.

یال‌های:

Code

D -- E
D -- F
E -- F

داخل Cycle هستند، پس Bridge نیستند.

اجرای شهودی مثال

Graph:

Code

A -- B -- C
     |
     D
    / \
   E---F

Triangle:

Code

D-E-F-D

Redundancy دارد.

اما اتصال بخش Triangle به B فقط:

Code

B -- D

است.

پس:

Code

B -- D

Bridge است.

Bridge در Tree

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

در هر Tree، تمام Edgeها Bridge هستند.

چرا؟

Tree هیچ Cycle ندارد.

پس برای هر Edge فقط یک مسیر ارتباطی وجود دارد.

حذف هر Edge، Tree را به دو Component تقسیم می‌کند.

Bridge در Complete Graph

در Complete Graph با حداقل سه Vertex:

Code

K_n

هیچ Bridgeای وجود ندارد.

چون بین هر دو بخش مسیرهای جایگزین زیادی داریم.

Graph زنجیره‌ای

Code

A -- B -- C -- D -- E

تمام Edgeها Bridge هستند.

Graph دارای Cycle و Tail

Code

A -- B
|    |
D -- C -- E -- F

Edgeهای Cycle:

Code

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

Bridge نیستند.

اما:

Code

C-E
E-F

Bridge هستند.

Graph Disconnected

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

برای همین:

JavaScript

for (const node of nodes) {
  if (!visited.has(node)) {
    dfs(node);
  }
}

لازم است.

Parent Edge چرا باید Ignore شود؟

در Graph بدون‌جهت:

Code

A -- B

اگر DFS از A به B برود، adjacency list در B دوباره A را نشان می‌دهد.

این Edge همان Edge والد است، نه Back Edge واقعی.

پس:

JavaScript

v !== parent.get(u)

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

مشکل MultiGraph

فرض کنید بین A و B دو Edge موازی داشته باشیم:

Code

A == B

اگر فقط Parent Vertex را Track کنیم، ممکن است Edge دوم را اشتباهاً Parent Edge حساب کنیم.

در MultiGraph بهتر است هر Edge یک ID مستقل داشته باشد.

نسخه مناسب MultiGraph با Edge ID

Representation:

JavaScript

const graph = {
  A: [
    { to: "B", id: 1 },
    { to: "B", id: 2 }
  ],
  B: [
    { to: "A", id: 1 },
    { to: "A", id: 2 }
  ]
};

در DFS به جای Parent Vertex، Parent Edge ID را نگه می‌داریم.

پیاده‌سازی Bridge برای MultiGraph

JavaScript

function findBridgesMultiGraph(graph) {
  const visited = new Set();
  const disc = new Map();
  const low = new Map();

  const bridges = [];

  let time = 0;

  function dfs(u, parentEdgeId = null) {
    visited.add(u);

    disc.set(u, ++time);
    low.set(u, disc.get(u));

    for (const edge of graph[u] ?? []) {
      const { to: v, id } = edge;

      if (id === parentEdgeId) {
        continue;
      }

      if (!visited.has(v)) {
        dfs(v, id);

        low.set(
          u,
          Math.min(
            low.get(u),
            low.get(v)
          )
        );

        if (
          low.get(v) > disc.get(u)
        ) {
          bridges.push(id);
        }
      } else {
        low.set(
          u,
          Math.min(
            low.get(u),
            disc.get(v)
          )
        );
      }
    }
  }

  for (const node of Object.keys(graph)) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }

  return bridges;
}

Self-loop

Edge:

Code

A -- A

Bridge نیست.

چون حذف آن Connectivity بین دو Vertex مختلف را از بین نمی‌برد.

Bridge و Redundancy

وجود Bridge معمولاً نشانه‌ی کمبود مسیر جایگزین است.

اگر یک Network هیچ Bridgeای نداشته باشد، از نظر Edge Connectivity نسبت به حذف یک Edge مقاوم‌تر است.

2-Edge-Connected Graph

یک Graph بدون‌جهت Connected که هیچ Bridgeای نداشته باشد:

Code

2-edge-connected

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

یعنی حذف هر یک Edge، Graph را disconnected نمی‌کند.

2-Edge-Connected Components

اگر تمام Bridgeها را حذف کنیم، Graph به بخش‌هایی تقسیم می‌شود که داخل هر بخش هیچ Bridgeای وجود ندارد.

این بخش‌ها:

Code

2-edge-connected components

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

Bridge Tree چیست؟

اگر هر 2-edge-connected component را به یک Node فشرده کنیم و Bridgeها را به عنوان Edge نگه داریم، ساختاری Tree-like می‌سازیم که معمولاً:

Code

Bridge Tree

یا:

Code

Bridge Forest

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

اگر Graph اولیه Connected باشد، نتیجه یک Tree است.

چرا Bridge Tree مهم است؟

برای Queryهای مختلف مفید است:

چند Bridge بین دو Node وجود دارد؟
اگر یک Bridge حذف شود کدام بخش جدا می‌شود؟
کدام Connectionها Critical هستند؟
چگونه Redundancy اضافه کنیم؟

کاربرد در Computer Networks

مدل:

Code

Router / Switch = Vertex
Physical Link = Edge

Bridgeها لینک‌هایی هستند که Failure آن‌ها Network Partition ایجاد می‌کند.

کاربرد:

Redundancy Analysis
Fault Tolerance
Network Planning
Backup Link Design

کاربرد در Data Center

فرض کنید دو Zone فقط یک لینک ارتباطی دارند.

Code

Zone A -- critical link -- Zone B

این Link Bridge است.

راه‌حل معماری ممکن است اضافه کردن:

Code

secondary path

باشد.

کاربرد در حمل‌ونقل

مدل:

Code

City / Intersection = Vertex
Road / Rail Link = Edge

اگر یک جاده تنها اتصال بین دو منطقه باشد، Bridge است.

قطع آن ممکن است یک Region را Isolate کند.

کاربرد در شبکه برق

در مدل ساده:

Code

Substation = Vertex
Transmission Line = Edge

Bridge می‌تواند خط انتقال ساختاری مهمی باشد.

اما در Power Grid واقعی، Flow، Capacity، Stability و Constraintهای فیزیکی هم مهم‌اند.

پس Graph Bridge فقط تحلیل Connectivity ساختاری است.

کاربرد در شبکه‌های مخابراتی

در Fiber Network:

Code

POP = Vertex
Fiber Link = Edge

Bridgeها Linkهایی هستند که قطعی آن‌ها بخش‌هایی از Network را Disconnect می‌کند.

کاربرد در Microservice / Service Mesh

اگر Service Connectivity را به‌صورت Undirected مدل کنیم، Bridge می‌تواند ارتباطی باشد که تنها مسیر بین دو Cluster سرویس است.

ولی چون Dependencyهای سرویس‌ها معمولاً Directed هستند، مدل باید دقیق انتخاب شود.

Bridge و MST

Bridge با Minimum Spanning Tree یکی نیست.

اما یک نکته جالب:

هر Bridge در Graph Connected باید در هر Spanning Tree وجود داشته باشد.

چرا؟

چون اگر Bridge را حذف کنیم، Graph disconnected می‌شود.

پس هیچ Spanning Tree نمی‌تواند بدون آن همه Vertexها را Connect کند.

آیا هر Edge در MST Bridge است؟

خیر.

MST خودش Tree است و تمام Edgeهای داخل MST برای همان Tree حیاتی‌اند.

اما ممکن است در Graph اصلی Edge جایگزین وجود داشته باشد.

پس Edgeی که در MST است الزاماً Bridge در Graph اصلی نیست.

Bridge و Cycle

یک قضیه مهم:

Code

Edge is a Bridge
⇔
Edge belongs to no cycle

برای Undirected Graph.

این یکی از بهترین شهودهای مسئله است.

Bridge و Articulation Point همیشه با هم هستند؟

نه لزوماً به صورت یک‌به‌یک.

ممکن است Vertex Articulation باشد ولی همه Edgeهایش Bridge نباشند.

مثلاً:

Code

    C
   / \
  A---B
   |
   D

A ممکن است Articulation باشد چون D را وصل می‌کند، ولی Edgeهای Triangle Bridge نیستند.

نسخه TypeScript

TypeScript

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

function findBridges(
  graph: Graph
): Array<[string, string]> {
  const nodes = new Set<string>();

  for (const [u, neighbors] of Object.entries(graph)) {
    nodes.add(u);

    for (const v of neighbors) {
      nodes.add(v);
    }
  }

  const visited = new Set<string>();
  const disc = new Map<string, number>();
  const low = new Map<string, number>();
  const parent = new Map<string, string>();

  const bridges: Array<[string, string]> = [];

  let time = 0;

  function dfs(u: string): void {
    visited.add(u);

    disc.set(u, ++time);
    low.set(u, disc.get(u)!);

    for (const v of graph[u] ?? []) {
      if (!visited.has(v)) {
        parent.set(v, u);

        dfs(v);

        low.set(
          u,
          Math.min(
            low.get(u)!,
            low.get(v)!
          )
        );

        if (
          low.get(v)! > disc.get(u)!
        ) {
          bridges.push([u, v]);
        }
      } else if (
        v !== parent.get(u)
      ) {
        low.set(
          u,
          Math.min(
            low.get(u)!,
            disc.get(v)!
          )
        );
      }
    }
  }

  for (const node of nodes) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }

  return bridges;
}

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

Tarjan DFS:

Code

Time = O(V + E)

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

پیچیدگی فضایی

ساختارهای:

visited
disc
low
parent
recursion stack

در حدود:

Code

O(V)

فضای کمکی نیاز دارند.

خطاهای رایج

1. استفاده از >= به جای >

برای Bridge باید:

Code

low[v] > disc[u]

باشد.

2. Parent Edge را Back Edge حساب کردن

در Undirected Graph باید Edge والد Ignore شود.

3. اجرای DFS فقط از یک Node

Graph ممکن است Disconnected باشد.

4. استفاده مستقیم روی Directed Graph

الگوریتم کلاسیک Bridge برای Undirected Graph است.

5. فراموش کردن MultiGraph

Parallel Edgeها نیاز به Edge ID دارند.

6. فرض کردن Degree کم یعنی Bridge

Bridge یک ویژگی Global Connectivity است، نه فقط Local Degree.

7. Nodeهای فقط موجود در Neighbor List

باید مجموعه کامل Vertexها ساخته شود.

8. Recursion Depth

Graph عمیق در JavaScript ممکن است Stack Overflow ایجاد کند.

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

وقتی:

Critical Network Link می‌خواهیم.
Redundancy تحلیل می‌کنیم.
Single Point of Failure در سطح Connection مهم است.
Road / Rail Network بررسی می‌کنیم.
Data Center Connectivity تحلیل می‌کنیم.
2-edge-connected components می‌خواهیم.
Bridge Tree می‌سازیم.
Network Partition Risk بررسی می‌کنیم.

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

اگر Vertex بحرانی می‌خواهیم:

Code

Articulation Points

اگر Shortest Path می‌خواهیم:

Code

BFS / Dijkstra

اگر Directed Mutual Connectivity مهم است:

Code

SCC

اگر Edge Weight و کمترین هزینه مطرح است:

Code

MST / Shortest Path

بسته به مسئله مناسب‌ترند.

جدول مقایسه

مفهوم	چه چیزی بررسی می‌شود؟	نتیجه
Bridge	Edge بحرانی	حذف Edge Graph را disconnectedتر می‌کند
Articulation Point	Vertex بحرانی	حذف Vertex Graph را disconnectedتر می‌کند
Connected Components	گروه‌های مستقل	Reachability در Undirected Graph
SCC	گروه‌های strongly connected	Mutual Reachability در Directed Graph
MST	کم‌هزینه‌ترین اتصال	Spanning Tree
2-edge-connected	مقاومت به حذف یک Edge	هیچ Bridge ندارد

جمع‌بندی

Bridge یا Cut Edge یالی است که حذف آن تعداد Connected Componentهای Graph را افزایش می‌دهد.

الگوریتم کلاسیک و بهینه با DFS و دو مقدار انجام می‌شود:

Code

disc[u]
low[u]

برای Tree Edge:

Code

u -- v

اگر:

Code

low[v] > disc[u]

باشد:

Code

(u, v) is a Bridge

این شرط یعنی Subtree v هیچ مسیر جایگزینی به u یا Ancestorهای آن ندارد.

Complexity:

Code

O(V + E)

است.

مهم‌ترین شهود:

Code

Edge روی Cycle باشد
→ Bridge نیست

Edge روی هیچ Cycle نباشد
→ Bridge است

و مهم‌ترین Pattern مسئله:

Code

اگر یک Connection قطع شود،
آیا بخشی از Network از بخش دیگر جدا می‌شود؟

→ Bridge Detection

در سیستم‌های واقعی، Bridge Detection می‌تواند نقطه شروع بسیار خوبی برای پیدا کردن لینک‌های حیاتی و طراحی Redundancy باشد.

Bridge یا Cut Edge یالی در یک گراف بدون‌جهت است که اگر حذف شود، تعداد Connected Componentهای گراف افزایش پیدا می‌کند.

به زبان ساده:

Bridge یک ارتباط حیاتی است که اگر قطع شود، بخشی از شبکه از بخش دیگر جدا می‌شود.

یک مثال ساده

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

Code

A -- B -- C
     |
     D

یال:

Code

A -- B

Bridge است.

چرا؟

اگر آن را حذف کنیم:

Code

A

B -- C
|
D

رأس A از بقیه Graph جدا می‌شود.

همین‌طور:

Code

B -- C

و:

Code

B -- D

نیز Bridge هستند.

تعریف دقیق

در یک Graph بدون‌جهت:

Code

G = (V, E)

یال:

Code

e = (u, v)

یک Bridge است اگر:

Code

components(G - e)
>
components(G)

یعنی حذف آن تعداد Componentها را بیشتر کند.

چرا Bridge مهم است؟

فرض کنید Graph نماینده‌ی یک شبکه واقعی باشد:

Code

Data Center = Vertex
Network Link = Edge

اگر فقط یک Link بین دو Zone وجود داشته باشد، قطع آن Link باعث Partition شدن شبکه می‌شود.

پس آن Link:

Code

Single Point of Failure

در سطح Edge است.

تفاوت Bridge با Articulation Point

Bridge

یک Edge بحرانی است.

Code

remove edge
→ connectivity decreases

Articulation Point

یک Vertex بحرانی است.

Code

remove vertex
→ connectivity decreases

پس:

Code

Bridge = critical edge
Articulation Point = critical vertex

روش ساده Brute Force

یک راه ساده برای پیدا کردن Bridgeها:

برای هر Edge:

Edge را موقتاً حذف کن.
تعداد Connected Componentها را حساب کن.
Edge را برگردان.
اگر Componentها بیشتر شدند، Edge یک Bridge است.

مشکل Brute Force

اگر E یال داشته باشیم و برای هر یال DFS/BFS کامل اجرا کنیم:

Code

O(E × (V + E))

می‌شود.

برای Graph بزرگ مناسب نیست.

روش بهینه: Tarjan + DFS

می‌توان همه Bridgeها را با یک DFS پیدا کرد.

Complexity:

Code

O(V + E)

مفاهیم اصلی:

Code

disc[u]
low[u]

هستند.

discovery time چیست؟

disc[u] زمان اولین Visit شدن رأس u در DFS است.

مثلاً:

Code

A → B → C → D

ممکن است:

Code

disc[A] = 1
disc[B] = 2
disc[C] = 3
disc[D] = 4

باشد.

low-link value چیست؟

low[u] کوچک‌ترین discovery time رأسی است که از Subtree مربوط به u می‌توان از طریق:

Tree Edgeهای DFS
و Back Edge

به آن رسید.

به زبان شهودی:

low نشان می‌دهد Subtree این Node چقدر می‌تواند به Ancestorهای قبلی یک مسیر جایگزین داشته باشد.

مثال برای low

فرض کنید:

Code

A
|
B
|
C
|
D

و Edge:

Code

D -- A

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

پس از D می‌توان مستقیم به A برگشت.

بنابراین:

Code

low[D] = disc[A]

و این مقدار به بالا منتقل می‌شود.

شرط Bridge

فرض کنید در DFS:

Code

u
|
v

و (u, v) یک Tree Edge باشد.

اگر:

Code

low[v] > disc[u]

آنگاه:

Code

(u, v) = Bridge

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

اگر:

Code

low[v] > disc[u]

باشد، یعنی Subtree مربوط به v هیچ Back Edgeای به u یا Ancestorهای u ندارد.

پس تنها راه اتصال آن Subtree به بخش بالای Graph همین Edge:

Code

u -- v

است.

اگر این Edge حذف شود، Subtree جدا می‌شود.

چرا شرط > است؟

این تفاوت را با Articulation Point باید دقیق یاد بگیریم.

برای Bridge:

Code

low[v] > disc[u]

برای Articulation Point غیرریشه:

Code

low[v] >= disc[u]

چرا؟

اگر:

Code

low[v] = disc[u]

باشد، Subtree می‌تواند با Back Edge به خود u برگردد.

در این حالت Edge (u,v) تنها راه اتصال نیست، پس Bridge نیست.

اما اگر خود u حذف شود، آن Back Edge هم از بین می‌رود؛ بنابراین u ممکن است Articulation Point باشد.

Tree Edge و Back Edge

در DFS دو نوع Edge مهم داریم.

Tree Edge

Edgeای که با آن برای اولین بار وارد یک Node جدید می‌شویم.

Code

u → v

که v قبلاً unvisited بوده.

Back Edge

Edgeای که از Node فعلی یا Subtree آن به Ancestor قبلی برمی‌گردد.

Back Edge نشانه‌ی وجود مسیر جایگزین است.

مثال Cycle

Graph:

Code

A -- B
|    |
D -- C

هیچ Edgeای Bridge نیست.

چرا؟

اگر هر Edge را حذف کنیم، هنوز از مسیر دیگر می‌توان بین Nodeها رفت.

مثلاً حذف:

Code

A -- B

باز هم:

Code

A → D → C → B

مسیر جایگزین است.

یک قانون مهم

در Graph بدون‌جهت:

Edgeای که روی هیچ Cycle قرار ندارد، Bridge است.

و بالعکس:

اگر Edge در یک Cycle باشد، Bridge نیست.

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

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

JavaScript

function findBridges(graph) {
  const nodes = new Set();

  for (const [u, neighbors] of Object.entries(graph)) {
    nodes.add(u);

    for (const v of neighbors) {
      nodes.add(v);
    }
  }

  const visited = new Set();
  const disc = new Map();
  const low = new Map();
  const parent = new Map();

  const bridges = [];

  let time = 0;

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

    disc.set(u, ++time);
    low.set(u, disc.get(u));

    for (const v of graph[u] ?? []) {
      if (!visited.has(v)) {
        parent.set(v, u);

        dfs(v);

        low.set(
          u,
          Math.min(
            low.get(u),
            low.get(v)
          )
        );

        if (
          low.get(v) > disc.get(u)
        ) {
          bridges.push([u, v]);
        }
      } else if (
        v !== parent.get(u)
      ) {
        low.set(
          u,
          Math.min(
            low.get(u),
            disc.get(v)
          )
        );
      }
    }
  }

  for (const node of nodes) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }

  return bridges;
}

مثال اجرا

JavaScript

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

console.log(findBridges(graph));

خروجی می‌تواند:

JSON

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

باشد.

یال‌های:

Code

D -- E
D -- F
E -- F

داخل Cycle هستند، پس Bridge نیستند.

اجرای شهودی مثال

Graph:

Code

A -- B -- C
     |
     D
    / \
   E---F

Triangle:

Code

D-E-F-D

Redundancy دارد.

اما اتصال بخش Triangle به B فقط:

Code

B -- D

است.

پس:

Code

B -- D

Bridge است.

Bridge در Tree

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

در هر Tree، تمام Edgeها Bridge هستند.

چرا؟

Tree هیچ Cycle ندارد.

پس برای هر Edge فقط یک مسیر ارتباطی وجود دارد.

حذف هر Edge، Tree را به دو Component تقسیم می‌کند.

Bridge در Complete Graph

در Complete Graph با حداقل سه Vertex:

Code

K_n

هیچ Bridgeای وجود ندارد.

چون بین هر دو بخش مسیرهای جایگزین زیادی داریم.

Graph زنجیره‌ای

Code

A -- B -- C -- D -- E

تمام Edgeها Bridge هستند.

Graph دارای Cycle و Tail

Code

A -- B
|    |
D -- C -- E -- F

Edgeهای Cycle:

Code

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

Bridge نیستند.

اما:

Code

C-E
E-F

Bridge هستند.

Graph Disconnected

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

برای همین:

JavaScript

for (const node of nodes) {
  if (!visited.has(node)) {
    dfs(node);
  }
}

لازم است.

Parent Edge چرا باید Ignore شود؟

در Graph بدون‌جهت:

Code

A -- B

اگر DFS از A به B برود، adjacency list در B دوباره A را نشان می‌دهد.

این Edge همان Edge والد است، نه Back Edge واقعی.

پس:

JavaScript

v !== parent.get(u)

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

مشکل MultiGraph

فرض کنید بین A و B دو Edge موازی داشته باشیم:

Code

A == B

اگر فقط Parent Vertex را Track کنیم، ممکن است Edge دوم را اشتباهاً Parent Edge حساب کنیم.

در MultiGraph بهتر است هر Edge یک ID مستقل داشته باشد.

نسخه مناسب MultiGraph با Edge ID

Representation:

JavaScript

const graph = {
  A: [
    { to: "B", id: 1 },
    { to: "B", id: 2 }
  ],
  B: [
    { to: "A", id: 1 },
    { to: "A", id: 2 }
  ]
};

در DFS به جای Parent Vertex، Parent Edge ID را نگه می‌داریم.

پیاده‌سازی Bridge برای MultiGraph

JavaScript

function findBridgesMultiGraph(graph) {
  const visited = new Set();
  const disc = new Map();
  const low = new Map();

  const bridges = [];

  let time = 0;

  function dfs(u, parentEdgeId = null) {
    visited.add(u);

    disc.set(u, ++time);
    low.set(u, disc.get(u));

    for (const edge of graph[u] ?? []) {
      const { to: v, id } = edge;

      if (id === parentEdgeId) {
        continue;
      }

      if (!visited.has(v)) {
        dfs(v, id);

        low.set(
          u,
          Math.min(
            low.get(u),
            low.get(v)
          )
        );

        if (
          low.get(v) > disc.get(u)
        ) {
          bridges.push(id);
        }
      } else {
        low.set(
          u,
          Math.min(
            low.get(u),
            disc.get(v)
          )
        );
      }
    }
  }

  for (const node of Object.keys(graph)) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }

  return bridges;
}

Self-loop

Edge:

Code

A -- A

Bridge نیست.

چون حذف آن Connectivity بین دو Vertex مختلف را از بین نمی‌برد.

Bridge و Redundancy

وجود Bridge معمولاً نشانه‌ی کمبود مسیر جایگزین است.

اگر یک Network هیچ Bridgeای نداشته باشد، از نظر Edge Connectivity نسبت به حذف یک Edge مقاوم‌تر است.

2-Edge-Connected Graph

یک Graph بدون‌جهت Connected که هیچ Bridgeای نداشته باشد:

Code

2-edge-connected

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

یعنی حذف هر یک Edge، Graph را disconnected نمی‌کند.

2-Edge-Connected Components

اگر تمام Bridgeها را حذف کنیم، Graph به بخش‌هایی تقسیم می‌شود که داخل هر بخش هیچ Bridgeای وجود ندارد.

این بخش‌ها:

Code

2-edge-connected components

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

Bridge Tree چیست؟

Code

Bridge Tree

یا:

Code

Bridge Forest

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

اگر Graph اولیه Connected باشد، نتیجه یک Tree است.

چرا Bridge Tree مهم است؟

برای Queryهای مختلف مفید است:

چند Bridge بین دو Node وجود دارد؟
اگر یک Bridge حذف شود کدام بخش جدا می‌شود؟
کدام Connectionها Critical هستند؟
چگونه Redundancy اضافه کنیم؟

کاربرد در Computer Networks

مدل:

Code

Router / Switch = Vertex
Physical Link = Edge

Bridgeها لینک‌هایی هستند که Failure آن‌ها Network Partition ایجاد می‌کند.

کاربرد:

Redundancy Analysis
Fault Tolerance
Network Planning
Backup Link Design

کاربرد در Data Center

فرض کنید دو Zone فقط یک لینک ارتباطی دارند.

Code

Zone A -- critical link -- Zone B

این Link Bridge است.

راه‌حل معماری ممکن است اضافه کردن:

Code

secondary path

باشد.

کاربرد در حمل‌ونقل

مدل:

Code

City / Intersection = Vertex
Road / Rail Link = Edge

اگر یک جاده تنها اتصال بین دو منطقه باشد، Bridge است.

قطع آن ممکن است یک Region را Isolate کند.

کاربرد در شبکه برق

در مدل ساده:

Code

Substation = Vertex
Transmission Line = Edge

Bridge می‌تواند خط انتقال ساختاری مهمی باشد.

اما در Power Grid واقعی، Flow، Capacity، Stability و Constraintهای فیزیکی هم مهم‌اند.

پس Graph Bridge فقط تحلیل Connectivity ساختاری است.

کاربرد در شبکه‌های مخابراتی

در Fiber Network:

Code

POP = Vertex
Fiber Link = Edge

Bridgeها Linkهایی هستند که قطعی آن‌ها بخش‌هایی از Network را Disconnect می‌کند.

کاربرد در Microservice / Service Mesh

اگر Service Connectivity را به‌صورت Undirected مدل کنیم، Bridge می‌تواند ارتباطی باشد که تنها مسیر بین دو Cluster سرویس است.

ولی چون Dependencyهای سرویس‌ها معمولاً Directed هستند، مدل باید دقیق انتخاب شود.

Bridge و MST

Bridge با Minimum Spanning Tree یکی نیست.

اما یک نکته جالب:

هر Bridge در Graph Connected باید در هر Spanning Tree وجود داشته باشد.

چرا؟

چون اگر Bridge را حذف کنیم، Graph disconnected می‌شود.

پس هیچ Spanning Tree نمی‌تواند بدون آن همه Vertexها را Connect کند.

آیا هر Edge در MST Bridge است؟

خیر.

MST خودش Tree است و تمام Edgeهای داخل MST برای همان Tree حیاتی‌اند.

اما ممکن است در Graph اصلی Edge جایگزین وجود داشته باشد.

پس Edgeی که در MST است الزاماً Bridge در Graph اصلی نیست.

Bridge و Cycle

یک قضیه مهم:

Code

Edge is a Bridge
⇔
Edge belongs to no cycle

برای Undirected Graph.

این یکی از بهترین شهودهای مسئله است.

Bridge و Articulation Point همیشه با هم هستند؟

نه لزوماً به صورت یک‌به‌یک.

ممکن است Vertex Articulation باشد ولی همه Edgeهایش Bridge نباشند.

مثلاً:

Code

    C
   / \
  A---B
   |
   D

A ممکن است Articulation باشد چون D را وصل می‌کند، ولی Edgeهای Triangle Bridge نیستند.

نسخه TypeScript

TypeScript

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

function findBridges(
  graph: Graph
): Array<[string, string]> {
  const nodes = new Set<string>();

  for (const [u, neighbors] of Object.entries(graph)) {
    nodes.add(u);

    for (const v of neighbors) {
      nodes.add(v);
    }
  }

  const visited = new Set<string>();
  const disc = new Map<string, number>();
  const low = new Map<string, number>();
  const parent = new Map<string, string>();

  const bridges: Array<[string, string]> = [];

  let time = 0;

  function dfs(u: string): void {
    visited.add(u);

    disc.set(u, ++time);
    low.set(u, disc.get(u)!);

    for (const v of graph[u] ?? []) {
      if (!visited.has(v)) {
        parent.set(v, u);

        dfs(v);

        low.set(
          u,
          Math.min(
            low.get(u)!,
            low.get(v)!
          )
        );

        if (
          low.get(v)! > disc.get(u)!
        ) {
          bridges.push([u, v]);
        }
      } else if (
        v !== parent.get(u)
      ) {
        low.set(
          u,
          Math.min(
            low.get(u)!,
            disc.get(v)!
          )
        );
      }
    }
  }

  for (const node of nodes) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }

  return bridges;
}

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

Tarjan DFS:

Code

Time = O(V + E)

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

پیچیدگی فضایی

ساختارهای:

visited
disc
low
parent
recursion stack

در حدود:

Code

O(V)

فضای کمکی نیاز دارند.

خطاهای رایج

1. استفاده از >= به جای >

برای Bridge باید:

Code

low[v] > disc[u]

باشد.

2. Parent Edge را Back Edge حساب کردن

در Undirected Graph باید Edge والد Ignore شود.

3. اجرای DFS فقط از یک Node

Graph ممکن است Disconnected باشد.

4. استفاده مستقیم روی Directed Graph

الگوریتم کلاسیک Bridge برای Undirected Graph است.

5. فراموش کردن MultiGraph

Parallel Edgeها نیاز به Edge ID دارند.

6. فرض کردن Degree کم یعنی Bridge

Bridge یک ویژگی Global Connectivity است، نه فقط Local Degree.

7. Nodeهای فقط موجود در Neighbor List

باید مجموعه کامل Vertexها ساخته شود.

8. Recursion Depth

Graph عمیق در JavaScript ممکن است Stack Overflow ایجاد کند.

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

وقتی:

Critical Network Link می‌خواهیم.
Redundancy تحلیل می‌کنیم.
Single Point of Failure در سطح Connection مهم است.
Road / Rail Network بررسی می‌کنیم.
Data Center Connectivity تحلیل می‌کنیم.
2-edge-connected components می‌خواهیم.
Bridge Tree می‌سازیم.
Network Partition Risk بررسی می‌کنیم.

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

اگر Vertex بحرانی می‌خواهیم:

Code

Articulation Points

اگر Shortest Path می‌خواهیم:

Code

BFS / Dijkstra

اگر Directed Mutual Connectivity مهم است:

Code

SCC

اگر Edge Weight و کمترین هزینه مطرح است:

Code

MST / Shortest Path

بسته به مسئله مناسب‌ترند.

جدول مقایسه

مفهوم	چه چیزی بررسی می‌شود؟	نتیجه
Bridge	Edge بحرانی	حذف Edge Graph را disconnectedتر می‌کند
Articulation Point	Vertex بحرانی	حذف Vertex Graph را disconnectedتر می‌کند
Connected Components	گروه‌های مستقل	Reachability در Undirected Graph
SCC	گروه‌های strongly connected	Mutual Reachability در Directed Graph
MST	کم‌هزینه‌ترین اتصال	Spanning Tree
2-edge-connected	مقاومت به حذف یک Edge	هیچ Bridge ندارد

جمع‌بندی

Bridge یا Cut Edge یالی است که حذف آن تعداد Connected Componentهای Graph را افزایش می‌دهد.

الگوریتم کلاسیک و بهینه با DFS و دو مقدار انجام می‌شود:

Code

disc[u]
low[u]

برای Tree Edge:

Code

u -- v

اگر:

Code

low[v] > disc[u]

باشد:

Code

(u, v) is a Bridge

این شرط یعنی Subtree v هیچ مسیر جایگزینی به u یا Ancestorهای آن ندارد.

Complexity:

Code

O(V + E)

است.

مهم‌ترین شهود:

Code

Edge روی Cycle باشد
→ Bridge نیست

Edge روی هیچ Cycle نباشد
→ Bridge است

و مهم‌ترین Pattern مسئله:

Code

اگر یک Connection قطع شود،
آیا بخشی از Network از بخش دیگر جدا می‌شود؟

→ Bridge Detection

Bridge در گراف چیست؟ پیدا کردن یال‌های بحرانی شبکه

یک مثال ساده

تعریف دقیق

چرا Bridge مهم است؟

تفاوت Bridge با Articulation Point

Bridge

Articulation Point

روش ساده Brute Force

مشکل Brute Force

روش بهینه: Tarjan + DFS

discovery time چیست؟

low-link value چیست؟

مثال برای low

شرط Bridge

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

چرا شرط > است؟

Tree Edge و Back Edge

Tree Edge

Back Edge

مثال Cycle

یک قانون مهم

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

مثال اجرا

اجرای شهودی مثال

Bridge در Tree

Bridge در Complete Graph

Graph زنجیره‌ای

Graph دارای Cycle و Tail

Graph Disconnected

Parent Edge چرا باید Ignore شود؟

مشکل MultiGraph

نسخه مناسب MultiGraph با Edge ID

پیاده‌سازی Bridge برای MultiGraph

Self-loop

Bridge و Redundancy

2-Edge-Connected Graph

2-Edge-Connected Components

Bridge Tree چیست؟

چرا Bridge Tree مهم است؟

کاربرد در Computer Networks

کاربرد در Data Center

کاربرد در حمل‌ونقل

کاربرد در شبکه برق

کاربرد در شبکه‌های مخابراتی

کاربرد در Microservice / Service Mesh

Bridge و MST

آیا هر Edge در MST Bridge است؟

Bridge و Cycle

Bridge و Articulation Point همیشه با هم هستند؟

نسخه TypeScript

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

پیچیدگی فضایی

خطاهای رایج

1. استفاده از >= به جای >

2. Parent Edge را Back Edge حساب کردن

3. اجرای DFS فقط از یک Node

4. استفاده مستقیم روی Directed Graph

5. فراموش کردن MultiGraph

6. فرض کردن Degree کم یعنی Bridge

7. Nodeهای فقط موجود در Neighbor List

8. Recursion Depth

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

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

جدول مقایسه

جمع‌بندی

Articulation Point چیست؟ پیدا کردن نقاط بحرانی شبکه

الگوریتم Bellman-Ford چیست؟ کوتاه‌ترین مسیر با وزن منفی

Bridge در گراف چیست؟ پیدا کردن یال‌های بحرانی شبکه

یک مثال ساده

تعریف دقیق

چرا Bridge مهم است؟

تفاوت Bridge با Articulation Point

Bridge

Articulation Point

روش ساده Brute Force

مشکل Brute Force

روش بهینه: Tarjan + DFS

discovery time چیست؟

low-link value چیست؟

مثال برای low