Cycle Detection یا تشخیص چرخه یکی از مهم‌ترین مسائل پایه در نظریه گراف و طراحی سیستم‌هاست.

سؤال اصلی ساده است:

آیا در گراف مسیری وجود دارد که از یک رأس شروع شود و دوباره به همان رأس یا یکی از رأس‌های مسیر فعلی برگردد؟

اگر چنین ساختاری وجود داشته باشد، یک Cycle داریم.

چرخه در بعضی مسائل کاملاً طبیعی و مجاز است؛ مثلاً مسیر رفت‌وبرگشت در شبکه حمل‌ونقل. اما در بعضی سیستم‌ها وجود Cycle نشانه‌ی یک خطای جدی است:

• Circular Dependency بین Packageها
• حلقه‌ی بی‌پایان در Workflow
• Dependency اشتباه بین Moduleها
• Cycle در Course Prerequisite
• ناسالم بودن یک DAG
• Loop در Build Pipeline
• وابستگی دوری بین سرویس‌ها

در این مقاله Cycle Detection را از پایه بررسی می‌کنیم و تفاوت روش‌های مناسب برای Directed Graph و Undirected Graph را می‌فهمیم. همچنین DFS، حالت‌های سه‌گانه، parent tracking، Union-Find، Kahn's Algorithm، پیدا کردن خود Cycle و کاربردهای واقعی را با JavaScript و TypeScript بررسی می‌کنیم.

Cycle دقیقاً چیست؟

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

A → B → C → D

در این Graph چرخه‌ای وجود ندارد.

اما اگر:

D → B

اضافه شود:

A → B → C → D
    ↑         |
    └─────────┘

حالا مسیر:

B → C → D → B

یک Cycle است.

چرا تشخیص Cycle مهم است؟

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

مثلاً:

Module A depends on Module B
Module B depends on Module C
Module C depends on Module A

یعنی:

A → B → C → A

در این حالت هیچ Module مستقلی وجود ندارد که بتوانیم اول Build کنیم.

پس قبل از Topological Sort یا Dependency Resolution باید بفهمیم Graph Cycle دارد یا نه.

تفاوت Cycle در Directed و Undirected Graph

این یکی از مهم‌ترین بخش‌های موضوع است.

Directed Graph

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

A → B
B → C
C → A

یک Cycle داریم.

Direction دقیق یال‌ها اهمیت دارد.

Undirected Graph

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

A -- B
|    |
C -- D

چرخه زمانی وجود دارد که بتوانیم با عبور از Edgeها دوباره به نقطه قبلی برگردیم بدون اینکه فقط همان Edge ورود را برگردیم.

در اینجا منطق Cycle Detection با Directed Graph فرق دارد.

اشتباه رایج: visited به تنهایی در Directed Graph کافی نیست

فرض کنید:

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

وقتی DFS از A شروع شود، ممکن است ابتدا:

A → B → D

را ببیند.

بعد به A برگردد و مسیر:

A → C → D

را بررسی کند.

D قبلاً visited شده است، اما Graph Cycle ندارد.

پس در Directed Graph، این منطق اشتباه است:

اگر neighbor visited بود → cycle

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

راه‌حل: سه State

برای Directed Graph معمولاً برای هر Node سه حالت نگه می‌داریم:

0 = unvisited
1 = visiting
2 = visited / finished

unvisited

هنوز DFS وارد Node نشده است.

visiting

Node در مسیر فعلی Recursion قرار دارد.

visited

DFS بررسی Node و تمام Descendantهای آن را تمام کرده است.

چرا رسیدن به visiting یعنی Cycle؟

فرض کنید:

A → B → C → D

و هنگام بررسی D به:

B

برسیم.

در این لحظه B هنوز visiting است.

یعنی B در مسیر فعلی DFS وجود دارد:

B → C → D → B

پس Cycle داریم.

این نوع Edge را معمولاً Back Edge می‌نامند.

Cycle Detection در Directed Graph با DFS

function hasCycleDirected(graph) {
  const state = new Map();

  function dfs(node) {
    const currentState = state.get(node) ?? 0;

    if (currentState === 1) {
      return true;
    }

    if (currentState === 2) {
      return false;
    }

    state.set(node, 1);

    for (const next of graph[node] ?? []) {
      if (dfs(next)) {
        return true;
      }
    }

    state.set(node, 2);

    return false;
  }

  for (const node of Object.keys(graph)) {
    if ((state.get(node) ?? 0) === 0) {
      if (dfs(node)) {
        return true;
      }
    }
  }

  return false;
}

اجرای مرحله‌به‌مرحله

فرض کنید:

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

شروع:

A = visiting

بعد:

B = visiting

بعد:

C = visiting

بعد:

D = visiting

از D دوباره به B می‌رسیم.

اما:

state[B] = visiting

پس:

B → C → D → B

یک Cycle است.

تفاوت visiting و visited

این تفاوت کلیدی است.

اگر به Nodeای برسیم که:

state = visited

است، آن Node قبلاً در یک DFS branch تمام شده.

این به خودی خود Cycle نیست.

اما اگر:

state = visiting

باشد، یعنی Node هنوز در recursion stack فعلی است.

پس Cycle داریم.

روش Recursion Stack

به‌جای Map سه‌حالته می‌توانیم دو Set داشته باشیم:

visited
recursionStack

function hasCycleDirectedWithStack(graph) {
  const visited = new Set();
  const active = new Set();

  function dfs(node) {
    if (active.has(node)) {
      return true;
    }

    if (visited.has(node)) {
      return false;
    }

    visited.add(node);
    active.add(node);

    for (const next of graph[node] ?? []) {
      if (dfs(next)) {
        return true;
      }
    }

    active.delete(node);

    return false;
  }

  for (const node of Object.keys(graph)) {
    if (dfs(node)) {
      return true;
    }
  }

  return false;
}

این همان منطق سه State است، فقط با Data Structure متفاوت.

Cycle Detection در Undirected Graph

در گراف بدون‌جهت منطق متفاوت است.

فرض کنید:

A -- B

اگر DFS از A به B برود، وقتی از B همسایه A را ببیند، نباید بگوییم Cycle داریم.

چون:

A

فقط Parent B است.

پس باید Parent را Track کنیم.

DFS + Parent برای Undirected Graph

function hasCycleUndirected(graph) {
  const visited = new Set();

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

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        if (dfs(next, node)) {
          return true;
        }
      } else if (next !== parent) {
        return true;
      }
    }

    return false;
  }

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

  return false;
}

چرا next !== parent؟

فرض کنید:

A -- B -- C

وقتی در B هستیم:

A

visited است.

اما A همان Parent است.

پس این Edge فقط Edgeای است که با آن وارد B شده‌ایم.

این Cycle نیست.

اگر در B به Node دیگری برسیم که:

• visited است
• Parent نیست

آن‌وقت Cycle داریم.

مثال Undirected Graph دارای Cycle

A -- B
|    |
D -- C

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

A → B → C → D

در D دوباره A را می‌بینیم.

A visited است و Parent D نیست.

پس:

A → B → C → D → A

یک Cycle است.

Cycle Detection با BFS در Undirected Graph

Cycle Detection فقط با DFS ممکن نیست.

با BFS هم می‌توان Parent را Track کرد.

function hasCycleUndirectedBFS(graph) {
  const visited = new Set();

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

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

    visited.add(start);

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

      for (const next of graph[node] ?? []) {
        if (!visited.has(next)) {
          visited.add(next);
          queue.push([next, node]);
        } else if (next !== parent) {
          return true;
        }
      }
    }
  }

  return false;
}

Union-Find برای Cycle Detection

در Undirected Graph یک روش بسیار مهم دیگر Disjoint Set Union (DSU) یا Union-Find است.

ایده:

برای هر Edge:

(u, v)

بررسی می‌کنیم آیا u و v از قبل در یک Component هستند یا نه.

اگر باشند، اضافه کردن Edge جدید یک Cycle می‌سازد.

مثال

Edgeها را به ترتیب اضافه می‌کنیم:

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

قبل از اضافه کردن:

D -- A

می‌بینیم D و A از قبل از طریق:

A → B → C → D

Connected هستند.

پس اضافه شدن Edge:

D -- A

یک Cycle می‌سازد.

پیاده‌سازی Union-Find

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;
  }
}

تشخیص Cycle با DSU

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

  for (const [u, v] of edges) {
    if (!dsu.union(u, v)) {
      return true;
    }
  }

  return false;
}

این روش برای Undirected Graph بسیار مناسب است.

چرا Union-Find برای Directed Graph کافی نیست؟

در Directed Graph فقط Connected بودن دو رأس معنای Cycle ندارد.

Direction اهمیت دارد.

مثلاً:

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

از نظر Connectivity ساختار مشترک داریم، ولی Cycle وجود ندارد.

Union-Find جهت Edgeها را مدل نمی‌کند.

پس برای Directed Graph معمولاً DFS سه‌حالته یا Kahn مناسب‌تر است.

Cycle Detection با Kahn's Algorithm

یک روش بسیار مهم برای Directed Graph، استفاده از Topological Sort با Kahn's Algorithm است.

ایده:

اگر Graph یک DAG باشد، باید بتوانیم همه Vertexها را Topologically Sort کنیم.

اگر بعد از Kahn هنوز بعضی Vertexها پردازش نشده باشند، Cycle داریم.

Kahn چگونه کار می‌کند؟

1. in-degree همه Nodeها را حساب کن.
2. همه Nodeهای با in-degree صفر را داخل Queue بگذار.
3. آن‌ها را حذف کن.
4. in-degree همسایه‌ها را کم کن.
5. اگر همسایه‌ای صفر شد، وارد Queue شود.
6. تعداد Nodeهای پردازش‌شده را بشمار.

اگر:

processedCount < V

یعنی Cycle وجود دارد.

JavaScript

function hasCycleKahn(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 indegree = new Map();

  for (const node of nodes) {
    indegree.set(node, 0);
  }

  for (const neighbors of Object.values(graph)) {
    for (const v of neighbors) {
      indegree.set(v, indegree.get(v) + 1);
    }
  }

  const queue = [];

  for (const node of nodes) {
    if (indegree.get(node) === 0) {
      queue.push(node);
    }
  }

  let head = 0;
  let processed = 0;

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

    for (const next of graph[node] ?? []) {
      indegree.set(
        next,
        indegree.get(next) - 1
      );

      if (indegree.get(next) === 0) {
        queue.push(next);
      }
    }
  }

  return processed !== nodes.size;
}

چرا Kahn وجود Cycle را مشخص می‌کند؟

در DAG همیشه حداقل یک Node با:

in-degree = 0

وجود دارد.

اما داخل یک Cycle مثل:

A → B → C → A

هر Node حداقل یک ورودی از Cycle دارد.

پس هیچ‌کدام نمی‌توانند آزاد شوند.

در نتیجه بعضی Nodeها هرگز وارد Queue نمی‌شوند.

DFS یا Kahn؟

هر دو برای Directed Cycle Detection مناسب‌اند.

DFS سه‌حالته

مناسب وقتی:

• Traversal DFS در الگوریتم دارید.
• می‌خواهید خود Cycle را بازسازی کنید.
• Recursion Stack اطلاعات بیشتری می‌دهد.

Kahn

مناسب وقتی:

• Topological Sort هم لازم دارید.
• با in-degree کار می‌کنید.
• Iterative solution می‌خواهید.

پیدا کردن خود Cycle

گاهی فقط:

true / false

کافی نیست.

مثلاً در Build System می‌خواهیم بگوییم:

Circular dependency:
A → B → C → A

برای این کار باید Parentها و recursion state را Track کنیم.

بازسازی Cycle در Directed Graph

function findDirectedCycle(graph) {
  const state = new Map();
  const parent = new Map();

  let cycleStart = null;
  let cycleEnd = null;

  function dfs(node) {
    state.set(node, 1);

    for (const next of graph[node] ?? []) {
      const nextState = state.get(next) ?? 0;

      if (nextState === 0) {
        parent.set(next, node);

        if (dfs(next)) {
          return true;
        }
      } else if (nextState === 1) {
        cycleStart = next;
        cycleEnd = node;

        return true;
      }
    }

    state.set(node, 2);

    return false;
  }

  for (const node of Object.keys(graph)) {
    if ((state.get(node) ?? 0) === 0) {
      if (dfs(node)) break;
    }
  }

  if (cycleStart === null) {
    return null;
  }

  const cycle = [cycleStart];
  let current = cycleEnd;

  while (current !== cycleStart) {
    cycle.push(current);
    current = parent.get(current);
  }

  cycle.push(cycleStart);

  return cycle.reverse();
}

ممکن است خروجی:

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

باشد.

Self-loop

ساده‌ترین Cycle:

A → A

است.

این یک Cycle با طول یک است.

در Directed Graph الگوریتم DFS سه‌حالته بلافاصله آن را تشخیص می‌دهد.

Parallel Edge در Undirected Graph

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

A == B

یعنی دو Edge مجزا بین A و B.

در بسیاری از تعریف‌ها این دو Edge می‌توانند یک Cycle طول دو بسازند.

پس اگر MultiGraph داریم، صرفاً مقایسه‌ی next !== parent ممکن است کافی نباشد.

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

Cycle در Disconnected Graph

ممکن است Graph چند Component داشته باشد:

A -- B

C -- D -- E
     |    |
     └────┘

اگر فقط DFS را از A اجرا کنیم، Cycle Component دوم را نمی‌بینیم.

پس باید از همه Nodeهای unvisited DFS شروع کنیم.

کاربرد واقعی: Circular Dependency

فرض کنید:

AuthService → UserService
UserService → EmailService
EmailService → AuthService

این Dependency Cycle است.

نتایج احتمالی:

• Build Failure
• Initialization Problem
• Runtime Loop
• Coupling شدید
• سخت شدن Testing

Cycle Detection می‌تواند در CI/CD یا Static Analysis قبل از Deploy این مشکل را پیدا کند.

Package Dependency

Package Managerها Dependency Graph دارند.

مثلاً:

package-a → package-b
package-b → package-c
package-c → package-a

باید Cycle تشخیص داده شود تا Dependency Resolution قابل مدیریت باشد.

Workflow Engine

فرض کنید:

Draft → Review → Approve → Draft

اگر این Loop آگاهانه طراحی نشده باشد، Workflow ممکن است هیچ‌وقت تمام نشود.

Cycle Detection می‌تواند قبل از Publish شدن Workflow ساختار آن را Validate کند.

Course Prerequisites

فرض کنید:

Algorithms → Data Structures
Data Structures → Programming
Programming → Algorithms

هیچ Courseای نمی‌تواند نقطه شروع باشد.

پس Prerequisite Graph Cycle دارد.

Build System

در Build Graph:

A depends on B
B depends on C
C depends on A

Build Order ممکن نیست.

Topological Sort شکست می‌خورد.

Spreadsheet Formula Dependencies

حتی Spreadsheetها می‌توانند Dependency Graph داشته باشند.

مثلاً:

A1 = B1 + 1
B1 = C1 + 1
C1 = A1 + 1

این یک Circular Reference است.

Cycle Detection دقیقاً همین ساختار را پیدا می‌کند.

Database Foreign Key Dependency

در طراحی Schema، بعضی Dependencyها می‌توانند ساختارهای Cyclic ایجاد کنند.

همیشه Cycle بد نیست، اما هنگام Migration، Insert Order یا Cascade باید آگاهانه مدیریت شود.

Microservices

اگر:

Service A → Service B
Service B → Service C
Service C → Service A

باشد، می‌تواند Coupling و Failure Propagation ایجاد کند.

Cycle Detection روی Service Dependency Graph برای Architecture Analysis مفید است.

آیا Cycle همیشه بد است؟

خیر.

در بعضی Domainها Cycle کاملاً طبیعی است.

مثلاً:

• Road Network
• Social Network
• State Machine
• Game Map
• Bidirectional Communication

مسئله فقط این است که بدانیم Cycle برای Domain ما:

Valid

است یا:

Invalid

تشخیص DAG

Directed Acyclic Graph (DAG) گراف جهت‌داری است که Cycle ندارد.

پس:

Directed Graph + No Cycle = DAG

برای Validate کردن DAG می‌توان:

• DFS سه‌حالته
• Kahn's Algorithm

استفاده کرد.

چرا DAG مهم است؟

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

• Build Order
• Task Scheduling
• Course Prerequisite
• Data Pipeline
• Git Commit Graph abstraction
• Dependency Resolution
• Workflow planning

Cycle و Topological Sort

یک Graph فقط زمانی Topological Ordering دارد که DAG باشد.

پس:

Cycle exists
→ no valid topological ordering

این رابطه بسیار مهم است.

Floyd's Cycle Detection چیست؟

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

Floyd's Tortoise and Hare

وجود دارد.

اما این الگوریتم معمولاً برای Graph عمومی نیست.

بیشتر برای ساختارهایی مثل:

• Linked List
• Functional Graph
• Sequence of next pointers

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

Floyd در Linked List

اگر هر Node فقط یک next داشته باشد، می‌توان دو Pointer استفاده کرد:

slow = slow.next
fast = fast.next.next

اگر Cycle وجود داشته باشد، در نهایت slow و fast به هم می‌رسند.

function hasCycleLinkedList(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) {
      return true;
    }
  }

  return false;
}

Floyd و Graph Cycle Detection

نباید Floyd را با Cycle Detection عمومی Graph اشتباه گرفت.

در Graph عمومی هر Node ممکن است چند Neighbor داشته باشد.

Floyd زمانی طبیعی است که هر State فقط یک Next State مشخص داشته باشد.

Complexity

DFS-based

با adjacency list:

Time = O(V + E)

چون هر Node و Edge تعداد محدودی پردازش می‌شود.

فضا:

O(V)

برای:

• state
• recursion stack
• parent

Kahn

Time = O(V + E)
Space = O(V)

Union-Find

برای E Edge:

O(E α(V))

تقریباً نزدیک خطی.

α(V) تابع Ackermann معکوس است و در عمل بسیار کوچک است.

Directed یا Undirected؛ کدام روش؟

TypeScript: Directed Cycle Detection

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

function hasCycleDirected(
  graph: Graph
): boolean {
  const state = new Map<string, number>();

  function dfs(node: string): boolean {
    const currentState = state.get(node) ?? 0;

    if (currentState === 1) {
      return true;
    }

    if (currentState === 2) {
      return false;
    }

    state.set(node, 1);

    for (const next of graph[node] ?? []) {
      if (dfs(next)) {
        return true;
      }
    }

    state.set(node, 2);

    return false;
  }

  for (const node of Object.keys(graph)) {
    if ((state.get(node) ?? 0) === 0) {
      if (dfs(node)) {
        return true;
      }
    }
  }

  return false;
}

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

1. استفاده فقط از visited در Directed Graph

visited بودن Neighbor الزاماً Cycle نیست.

باید بدانیم Node در recursion path فعلی است یا نه.

2. فراموش کردن Parent در Undirected Graph

بدون Parent، Edge برگشت به Parent ممکن است اشتباهاً Cycle محسوب شود.

3. بررسی فقط یک Component

Graph می‌تواند Disconnected باشد.

4. استفاده از Union-Find برای Directed Graph

Union-Find Direction را مدل نمی‌کند.

5. تشخیص Cycle بدون بازسازی مسیر

در Production گاهی دانستن اینکه Cycle وجود دارد کافی نیست؛ باید Cycle دقیق را گزارش کنیم.

6. Recursion Depth

در Graphهای بسیار عمیق، Recursive DFS می‌تواند Stack Overflow بدهد.

7. MultiGraph

Parallel Edgeها به Edge ID نیاز دارند تا منطق Parent اشتباه نشود.

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

وقتی:

• Dependency Graph داریم.
• Workflow باید acyclic باشد.
• DAG را Validate می‌کنیم.
• Build Order می‌خواهیم.
• Circular Dependency مهم است.
• Course Prerequisite داریم.
• Task Scheduling داریم.
• Package Dependency بررسی می‌کنیم.
• Linked List Cycle می‌خواهیم.
• Architecture Graph تحلیل می‌کنیم.

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

اگر فقط می‌خواهیم Reachability را بفهمیم:

DFS / BFS

کافی است.

اگر می‌خواهیم همه SCCها را پیدا کنیم:

Tarjan / Kosaraju

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

اگر می‌خواهیم Topological Order واقعی تولید کنیم:

Topological Sort

را اجرا می‌کنیم، هرچند Cycle Detection بخشی از Validation آن است.

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

جمع‌بندی

Cycle Detection یکی از اساسی‌ترین الگوهای Graph Algorithm است.

اما نکته‌ی مهم این است که «Cycle Detection» فقط یک الگوریتم واحد نیست.

روش مناسب به نوع Graph بستگی دارد:

Directed
→ visiting / visited
→ recursion stack
→ Kahn

Undirected
→ parent tracking
→ Union-Find

Linked List
→ Floyd

در Directed Graph، مهم‌ترین ایده تفاوت بین:

visiting

و:

visited

است.

رسیدن به visiting یعنی Back Edge و در نتیجه Cycle.

در Undirected Graph باید Edge بازگشت به Parent را از Cycle واقعی جدا کنیم.

با adjacency list، DFS و Kahn معمولاً در:

O(V + E)

اجرا می‌شوند.

اما ارزش اصلی این موضوع در سیستم‌های واقعی است؛ جایی که Cycle می‌تواند نشانه‌ی:

Circular Dependency
Invalid Workflow
Impossible Build Order
Invalid DAG
Circular Reference

باشد.

پس Pattern تشخیص مسئله ساده است:

آیا وجود یک Loop در روابط سیستم می‌تواند ترتیب، Dependency یا Execution را خراب کند؟

→ Cycle Detection