Topological Sorting یا مرتب‌سازی توپولوژیک یکی از مهم‌ترین الگوریتم‌ها برای کار با وابستگی‌ها در گراف‌های جهت‌دار است.

صورت ساده‌ی مسئله این است:

اگر انجام B به A وابسته باشد، A باید قبل از B قرار بگیرد.

مثلاً اگر برای Build کردن یک پروژه ابتدا باید Packageهای پایه نصب شوند، یا اگر برای گرفتن درس «هوش مصنوعی» ابتدا باید «ساختمان داده» پاس شده باشد، با یک Dependency Graph روبه‌رو هستیم.

Topological Sort ترتیبی از رأس‌ها می‌سازد که تمام این وابستگی‌ها را رعایت کند.

اما یک نکته بسیار مهم وجود دارد:

Topological Sort فقط برای DAG معنا دارد.

یعنی:

Directed Acyclic Graph

یک گراف جهت‌دار که Cycle نداشته باشد.

در این مقاله Topological Sorting را از صفر بررسی می‌کنیم؛ از مفهوم DAG و in-degree گرفته تا Kahn's Algorithm، روش DFS + Postorder، تشخیص Cycle، چند ترتیب معتبر، Unique Topological Order، کاربردهای واقعی و پیاده‌سازی JavaScript و TypeScript.

Topological Sort دقیقاً چه مسئله‌ای را حل می‌کند؟

فرض کنید چهار Task داریم:

Install Dependencies
Compile
Test
Deploy

و Dependencyها:

Install Dependencies → Compile
Compile → Test
Test → Deploy

واضح است که ترتیب زیر معتبر است:

Install Dependencies
→ Compile
→ Test
→ Deploy

اما:

Deploy
→ Test
→ Compile

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

Topological Sort دقیقاً می‌خواهد یک ترتیب خطی پیدا کند که:

برای هر Edge:

u → v

رأس u قبل از v قرار بگیرد.

تعریف رسمی

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

G = (V, E)

باشد، یک Topological Ordering ترتیبی از تمام رأس‌هاست که برای هر Edge:

u → v

داریم:

position(u) < position(v)

یعنی u در ترتیب نهایی قبل از v قرار دارد.

چرا فقط Directed Graph؟

در Dependency معمولاً Relation جهت دارد.

مثلاً:

A → B

یعنی:

B depends on A

پس A باید قبل از B باشد.

در Graph بدون جهت چنین مفهوم «قبل و بعد» طبیعی وجود ندارد.

چرا Graph باید Acyclic باشد؟

فرض کنید:

A → B
B → C
C → A

از Dependencyها داریم:

A before B
B before C
C before A

اما این یعنی:

A < B < C < A

که غیرممکن است.

پس:

Cycle exists
→ No valid topological ordering

و:

Topological ordering exists
→ Graph is a DAG

یک مثال ساده

Graph:

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

Dependencyها:

A قبل از C
B قبل از C
B قبل از D
C قبل از E
D قبل از E

یک Topological Order معتبر:

A, B, C, D, E

اما این تنها جواب نیست.

مثلاً:

B, A, D, C, E

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

آیا Topological Sort همیشه Unique است؟

خیر.

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

مثلاً:

A → C
B → C

دو ترتیب معتبر:

A, B, C

و:

B, A, C

هستند.

پس Topological Sort معمولاً:

One of many valid orders

را برمی‌گرداند.

روش اول: Kahn's Algorithm

یکی از مشهورترین روش‌ها برای Topological Sorting الگوریتم Kahn است.

ایده اصلی بر پایه‌ی:

in-degree

است.

in-degree چیست؟

در Directed Graph:

in-degree(v)

یعنی تعداد Edgeهایی که وارد v می‌شوند.

مثلاً:

A → C
B → C

داریم:

inDegree(A) = 0
inDegree(B) = 0
inDegree(C) = 2

چرا Node با in-degree صفر مهم است؟

اگر:

inDegree(A) = 0

باشد، یعنی A هیچ Dependency حل‌نشده‌ای ندارد.

پس می‌توانیم A را همین الان اجرا کنیم.

این دقیقاً ایده Kahn است:

هر بار یک Node بدون Dependency باقی‌مانده پیدا کن، آن را از Graph حذف کن، سپس Dependencyهای وابسته به آن را Update کن.

مراحل Kahn's Algorithm

1. in-degree تمام Nodeها را حساب کن.
2. تمام Nodeهای in-degree = 0 را داخل Queue بگذار.
3. یک Node را از Queue بردار.
4. آن را وارد Topological Order کن.
5. Edgeهای خروجی آن را حذف‌شده فرض کن.
6. in-degree همسایه‌ها را یک واحد کم کن.
7. هر همسایه‌ای که in-degree = 0 شد وارد Queue شود.
8. تا خالی شدن Queue ادامه بده.

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

Graph:

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

ابتدا:

A = 0
B = 0
C = 2
D = 1
E = 2

Queue:

[A, B]

فرض کنیم A را برداریم:

order = [A]

Edge:

A → C

حذف می‌شود.

پس:

C: 2 → 1

بعد B:

order = [A, B]

Edgeهای B:

B → C
B → D

پس:

C: 1 → 0
D: 1 → 0

Queue:

[C, D]

بعد C و D پردازش می‌شوند و در نهایت E آزاد می‌شود.

نتیجه ممکن است:

[A, B, C, D, E]

باشد.

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

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

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

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

  const indegree = new Map();

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

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

  const queue = [];

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

  let head = 0;
  const order = [];

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

    order.push(current);

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

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

  if (order.length !== nodes.size) {
    return null;
  }

  return order;
}

اگر null برگردد:

Cycle exists

چرا Kahn می‌تواند Cycle را تشخیص دهد؟

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

in-degree = 0

وجود دارد.

اگر هیچ Node با indegree صفر باقی نمانده باشد ولی هنوز Node پردازش‌نشده داریم، یعنی آن Nodeها به شکل Cyclic به هم وابسته‌اند.

مثلاً:

A → B
B → C
C → A

داریم:

A = 1
B = 1
C = 1

Queue از ابتدا خالی است.

پس:

processed = 0
V = 3

و نتیجه:

Cycle

است.

نکته JavaScript: چرا shift استفاده نکردیم؟

می‌توانستیم بنویسیم:

queue.shift()

اما برای Queue بزرگ، shift() می‌تواند پرهزینه باشد چون Array باید جابه‌جا شود.

پس از Index استفاده کردیم:

let head = 0;

const current = queue[head++];

این الگو برای BFS و Kahn در JavaScript مناسب‌تر است.

روش دوم: Topological Sort با DFS

Topological Sort را می‌توان با DFS نیز ساخت.

ایده:

یک Node را زمانی وارد نتیجه کن که تمام Dependencyهای بعد از آن بررسی شده باشند.

یعنی Node را در Postorder وارد Stack می‌کنیم.

DFS Postorder

فرض کنید:

A → B → C

DFS:

A
↓
B
↓
C

اول C تمام می‌شود:

finish C

بعد B:

finish B

بعد A:

finish A

Finish Order:

C, B, A

Reverse:

A, B, C

که Topological Order است.

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

نسخه آموزشی:

function topologicalSortDFS(graph) {
  const visited = new Set();
  const order = [];

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

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

    order.push(node);
  }

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

  return order.reverse();
}

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

Cycle را تشخیص نمی‌دهد.

برای Production باید Cycle Detection اضافه شود.

DFS سه‌حالته برای Topological Sort

برای Directed Graph از سه State استفاده می‌کنیم:

0 = unvisited
1 = visiting
2 = finished

اگر هنگام DFS به Node با state برابر 1 برسیم:

Cycle exists

نسخه کامل DFS + Cycle Detection

function topologicalSortDFS(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 state = new Map();
  const order = [];

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

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

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

    state.set(node, 1);

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

    state.set(node, 2);
    order.push(node);

    return true;
  }

  for (const node of nodes) {
    if ((state.get(node) ?? 0) === 0) {
      if (!dfs(node)) {
        return null;
      }
    }
  }

  return order.reverse();
}

Kahn یا DFS؟

هر دو:

O(V + E)

هستند.

اما تفاوت‌های عملی دارند.

Topological Sort و DAG

Topological Sort و DAG رابطه مستقیم دارند:

Graph is DAG
⇔
Topological Ordering exists

این رابطه در بسیاری از مسائل Interview و Production مهم است.

مثال Course Prerequisites

فرض کنید درس‌ها:

Programming
Data Structures
Algorithms
AI

Dependency:

Programming → Data Structures
Data Structures → Algorithms
Algorithms → AI

ترتیب معتبر:

Programming
→ Data Structures
→ Algorithms
→ AI

اگر اضافه کنیم:

AI → Programming

Cycle ایجاد می‌شود و Curriculum غیرممکن می‌شود.

Course Schedule Problem

یکی از مسائل معروف:

آیا می‌توان تمام Courseها را با توجه به Prerequisiteها تمام کرد؟

در اصل سؤال این است:

Is prerequisite graph a DAG?

اگر Kahn تمام Courseها را Process کند:

Yes

اگر نه:

Cycle exists

Build System

فرض کنید:

core
↓
utils
↓
api
↓
frontend

Build باید Dependencyها را رعایت کند.

مثلاً:

core
utils
api
frontend

Topological Sort ترتیب Build را تولید می‌کند.

ابزارهایی مثل Build Systemها، Package Graphها و Monorepo tooling از همین الگو استفاده می‌کنند.

Package Dependency

مثلاً:

react-app
→ ui-library
→ shared-utils

اگر:

shared-utils
→ react-app

اضافه شود:

Circular Dependency

داریم.

پس Topological Sort می‌تواند Dependency Graph را هم ترتیب دهد و هم Validate کند.

CI/CD Jobs

فرض کنید Pipeline:

Install
↓
Lint
↓
Test
↓
Build
↓
Deploy

اما بعضی Jobها Parallel هستند:

Lint
Test

ممکن است هر دو بعد از Install اجرا شوند.

Graph:

Install → Lint
Install → Test
Lint → Build
Test → Build
Build → Deploy

Topological Ordering dependency order را می‌دهد.

Topological Levels برای Parallel Execution

گاهی فقط ترتیب خطی نمی‌خواهیم.

می‌خواهیم بفهمیم چه Taskهایی می‌توانند Parallel اجرا شوند.

در Kahn می‌توان Nodeهای indegree صفر فعلی را یک Level در نظر گرفت.

مثلاً:

Level 0:
Install

Level 1:
Lint, Test

Level 2:
Build

Level 3:
Deploy

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

پیاده‌سازی Topological Levels

function topologicalLevels(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 next of neighbors) {
      indegree.set(
        next,
        indegree.get(next) + 1
      );
    }
  }

  let current = [...nodes].filter(
    node => indegree.get(node) === 0
  );

  const levels = [];
  let processed = 0;

  while (current.length > 0) {
    levels.push(current);
    processed += current.length;

    const nextLevel = [];

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

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

    current = nextLevel;
  }

  return processed === nodes.size
    ? levels
    : null;
}

Workflow Engine

فرض کنید:

Draft
→ Review
→ Legal Approval
→ Publish

Topological Sort می‌تواند ترتیب معتبر Stepها را تعیین کند.

اگر بعضی Stepها مستقل باشند، Scheduler می‌تواند آن‌ها را Parallel کند.

ETL و Data Pipeline

در Data Engineering:

Extract
→ Clean
→ Aggregate
→ Train Model
→ Publish Metrics

هر Stage به Stageهای قبلی وابسته است.

Pipeline معمولاً یک DAG است.

Topological Sorting کمک می‌کند:

• ترتیب اجرا مشخص شود.
• Dependencyهای آماده شناسایی شوند.
• Jobهای Parallel پیدا شوند.
• Cycleهای اشتباه Detect شوند.

Task Scheduling

فرض کنید:

Task A before Task D
Task B before Task D
Task C before Task E

Topological Sort یک ترتیب معتبر می‌دهد.

اما توجه کنید:

Topological Sort زمان‌بندی کامل Resourceها نیست.

اگر مواردی مثل:

• CPU capacity
• worker count
• deadline
• task duration
• priority

داشته باشیم، Scheduling Problem پیچیده‌تر می‌شود.

Topological Sort و Shortest Path در DAG

یکی از کاربردهای جالب Topological Order این است که Shortest Path در DAG را می‌توان بسیار سریع محاسبه کرد.

مراحل:

1. Topological Sort بگیر.
2. Nodeها را به همان ترتیب پردازش کن.
3. Edgeها را Relax کن.

حتی Weight منفی هم در DAG مشکل Cycle منفی ایجاد نمی‌کند، چون اصلاً Cycle نداریم.

Complexity:

O(V + E)

است.

Longest Path در DAG

در Graph عمومی Longest Path مسئله سختی است.

اما در DAG می‌توان با Topological Order آن را با Dynamic Programming حل کرد.

مثلاً برای Critical Path در Pipeline:

dp[v] =
max(
  dp[u] + weight(u, v)
)

برای Edgeهای ورودی به v.

این پایه‌ی بسیاری از مسائل Scheduling است.

Critical Path

اگر Taskها Duration داشته باشند:

A = 3h
B = 2h
C = 5h

Longest Path در Dependency DAG می‌تواند حداقل زمان کلی Project را در حالت Parallel مناسب مشخص کند.

چند Topological Order مختلف

اگر Queue در Kahn بیش از یک Node داشته باشد:

[A, B]

یعنی در آن لحظه بیش از یک انتخاب معتبر داریم.

این نشان می‌دهد ممکن است Topological Order یکتا نباشد.

چگونه بفهمیم Topological Order یکتا است؟

در Kahn اگر در هر مرحله دقیقاً یک Node با indegree صفر وجود داشته باشد، Order یکتا است.

اگر در یک مرحله:

queue size > 1

باشد، حداقل دو انتخاب داریم.

بررسی Unique Topological Order

function uniqueTopologicalOrder(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 next of neighbors) {
      indegree.set(
        next,
        indegree.get(next) + 1
      );
    }
  }

  const queue = [...nodes].filter(
    node => indegree.get(node) === 0
  );

  let head = 0;
  let processed = 0;
  let unique = true;

  while (head < queue.length) {
    const available = queue.length - head;

    if (available > 1) {
      unique = false;
    }

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

  if (processed !== nodes.size) {
    return {
      exists: false,
      unique: false
    };
  }

  return {
    exists: true,
    unique
  };
}

نکته: برای بررسی دقیق uniqueness با یک Queue معمولی باید «تعداد انتخاب‌های همزمان در هر مرحله» را درست مدیریت کنیم؛ در سیستم‌های جدی بهتر است frontier هر مرحله صریح نگه داشته شود.

Lexicographically Smallest Topological Order

گاهی چند جواب معتبر داریم اما می‌خواهیم کوچک‌ترین ترتیب lexicographic را انتخاب کنیم.

مثلاً:

A, B, C

را به:

B, A, C

ترجیح دهیم.

در Kahn کافی است به جای Queue معمولی از:

Min-Heap / Priority Queue

استفاده کنیم.

هر بار کوچک‌ترین Node با indegree صفر را انتخاب می‌کنیم.

آیا وزن Edge در Topological Sort مهم است؟

برای خود Topological Ordering:

No

چون فقط Dependency مهم است.

اما بعد از گرفتن Order ممکن است Weightها برای:

• shortest path
• longest path
• scheduling
• cost propagation

استفاده شوند.

Edge Case: Graph خالی

اگر:

V = 0

باشد، Topological Order:

[]

است.

Edge Case: یک Node

A

ترتیب:

[A]

است.

Edge Case: Node بدون outgoing edge

کاملاً طبیعی است.

مثلاً:

A: ["B"],
B: []

هر دو Node باید در nodes حساب شوند.

اشتباه رایج: فقط Object.keys(graph)

فرض کنید:

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

اگر فقط:

Object.keys(graph)

را Nodeها بدانیم، B را از دست می‌دهیم.

پس باید Nodeهایی که فقط در adjacency list ظاهر شده‌اند هم اضافه کنیم.

در کدهای کامل بالا همین کار را انجام دادیم.

Edge Case: Self-loop

A → A

یک Cycle است.

پس Topological Order وجود ندارد.

Edge Case: Duplicate Edge

اگر:

A → B
A → B

دو بار ثبت شده باشد، indegree B دوبار زیاد می‌شود.

اگر Graph منطقی Simple Graph است، باید Duplicate Edgeها را قبل از محاسبه حذف کنیم.

اگر MultiGraph است، باید Semantics را دقیق تعریف کنیم.

Topological Sort روی Disconnected DAG

Graph لازم نیست Connected باشد.

مثلاً:

A → B

C → D

Topological Sort همچنان ممکن است.

مثلاً:

A, C, B, D

یا:

C, A, D, B

فرق Topological Sort با Sorting معمولی

Topological Sort مثل:

Array.sort()

نیست.

در Sorting معمولی یک Comparison Order کامل داریم.

مثلاً:

1 < 2 < 3

اما در DAG ممکن است بین A و B هیچ Relationی وجود نداشته باشد.

پس Topological Sort یک:

Partial Order → Linear Extension

می‌سازد.

Partial Order چیست؟

Dependencyها فقط بعضی روابط «قبل از» را تعریف می‌کنند.

مثلاً:

A before C
B before C

اما درباره‌ی A و B چیزی نمی‌گویند.

Topological Sort یکی از ترتیب‌های خطی سازگار با این Partial Order را تولید می‌کند.

کاربرد در Spreadsheet Formula Graph

فرض کنید:

C1 = A1 + B1
D1 = C1 * 2

Dependency:

A1 → C1
B1 → C1
C1 → D1

برای Recalculate کردن سلول‌ها باید Dependency Order رعایت شود.

Topological Sort ابزار طبیعی این مسئله است.

اگر:

A1 depends on D1

اضافه شود، Circular Reference داریم.

Compiler و Module Graph

در Compiler یا Bundler ممکن است Moduleها Dependency داشته باشند:

main
→ auth
→ utils

Topological Order می‌تواند ترتیب پردازش Dependencyها را مشخص کند.

اما سیستم‌های واقعی ممکن است Cycle را با Strategyهای خاص مدیریت کنند، پس همیشه وجود Cycle به معنای Crash نیست؛ به Semantics ابزار بستگی دارد.

Database Migration

Migrationها ممکن است Dependency داشته باشند:

create users
→ create orders
→ add foreign keys
→ seed data

Topological Ordering می‌تواند ترتیب اعمال Migrationها را مشخص کند.

Infrastructure as Code

Resourceها:

Network
→ Database
→ Backend
→ Load Balancer

Dependency Graph می‌تواند برای ترتیب Provisioning استفاده شود.

Microservice Deployment

مثلاً:

Database
→ Auth Service
→ API Gateway

اگر Dependency Deployment صریح باشد، Topological Order می‌تواند ترتیب Deployment را مشخص کند.

ولی Runtime Dependencyهای Serviceها لزوماً نباید با Deployment Order یکی گرفته شوند.

پیچیدگی Kahn

با adjacency list:

Time = O(V + E)

چون:

• indegree همه Edgeها یک بار محاسبه می‌شود.
• هر Node یک بار پردازش می‌شود.
• هر Edge یک بار برای کم کردن indegree بررسی می‌شود.

فضای کمکی:

O(V)

برای:

• indegree
• queue
• output

و اگر Graph را هم حساب کنیم:

O(V + E)

پیچیدگی DFS Topological Sort

همان:

Time = O(V + E)

و:

Space = O(V)

برای:

• state
• recursion stack
• output

است.

Recursive DFS و Stack Overflow

اگر Dependency Graph بسیار عمیق باشد:

A1 → A2 → A3 → ... → A100000

Recursive DFS در JavaScript ممکن است Stack Overflow بدهد.

در چنین شرایطی:

• Kahn
• یا DFS Iterative

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

نسخه TypeScript با Kahn

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

function topologicalSort(
  graph: Graph
): string[] | null {
  const nodes = new Set<string>();

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

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

  const indegree = new Map<string, number>();

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

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

  const queue: string[] = [];

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

  let head = 0;
  const order: string[] = [];

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

    order.push(current);

    for (const next of graph[current] ?? []) {
      const value =
        (indegree.get(next) ?? 0) - 1;

      indegree.set(next, value);

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

  return order.length === nodes.size
    ? order
    : null;
}

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

1. اجرای Topological Sort روی Graph دارای Cycle

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

2. فراموش کردن Nodeهایی که فقط Destination هستند

مثل:

A: ["B"]

که B ممکن است key مستقل نداشته باشد.

3. استفاده از DFS بدون Cycle Detection

خروجی ممکن است ظاهراً Order بدهد، ولی Graph واقعاً DAG نباشد.

4. فرض کردن Topological Order یکتا است

ممکن است صدها Order معتبر وجود داشته باشد.

5. استفاده از shift برای Queue بزرگ در JavaScript

بهتر است head index استفاده شود.

6. اشتباه گرفتن Topological Sort با Shortest Path

Topological Sort فقط Order dependency می‌سازد.

7. اشتباه گرفتن Direction Edge

اگر:

A must happen before B

معمولاً Edge:

A → B

است.

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

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

وقتی:

• Dependency جهت‌دار داریم.
• Graph باید DAG باشد.
• Build Order می‌خواهیم.
• Course Prerequisite داریم.
• Job Scheduling بر اساس Dependency داریم.
• CI/CD Pipeline داریم.
• ETL/Data Pipeline داریم.
• Workflow Stepها Order دارند.
• Module Dependency می‌خواهیم.
• Spreadsheet Recalculation داریم.
• DAG DP اجرا می‌کنیم.

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

اگر Graph دارای Cycle است و Cycle بخشی طبیعی از Domain است، Topological Order کامل وجود ندارد.

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

DFS / BFS

کافی است.

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

Dijkstra / Bellman-Ford

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

اگر Dependencyها نیاز به Resource Scheduling، Deadline و Duration دارند، Topological Sort فقط یکی از مراحل مسئله است.

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

جمع‌بندی

Topological Sorting برای مرتب‌کردن Dependencyهای یک DAG استفاده می‌شود.

قانون اصلی:

u → v

یعنی:

u باید قبل از v قرار بگیرد.

دو روش اصلی:

Kahn
→ in-degree
→ Queue

DFS
→ Postorder
→ Reverse Finish Order

هر دو با adjacency list در:

O(V + E)

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

Kahn به‌صورت طبیعی Cycle را با تعداد Nodeهای پردازش‌شده تشخیص می‌دهد و برای Level Scheduling بسیار مناسب است.

DFS نیز با Stateهای:

unvisited
visiting
finished

می‌تواند هم Topological Order بسازد و هم Cycle را تشخیص دهد.

مهم‌ترین Pattern برای تشخیص مسئله:

آیا Taskها Dependency دارند؟
آیا باید چیزی قبل از چیز دیگری انجام شود؟
آیا می‌خواهیم Build / Course / Job / Pipeline را با رعایت وابستگی مرتب کنیم؟

→ Topological Sort

و همیشه قبل از نتیجه نهایی این سؤال را بپرسید:

آیا Graph واقعاً DAG است؟