מיון טופולוגי - סידור תלויות בגרף מכוון

Topological Sort הוא סידור של צמתי גרף מכוון אציקלי (DAG) כך שכל קשת (u → v) מופיעה עם u לפני v. זה פותר בעיות תלויות: סדר לימוד קורסים, סדר בנייה ב-Makefile, סדר import בין מודולים.

אלגוריתם 1 - Kahn's Algorithm (BFS)

בנוי על מושג in-degree: ספירת הקשתות הנכנסות לכל צומת. צמתים עם in-degree 0 (אין להם תלויות) נכנסים ראשונים לתור.

function topoSortKahn(n, edges) {
  const adj = Array.from({length: n}, () => []);
  const inDegree = new Array(n).fill(0);
  for (const [u, v] of edges) { adj[u].push(v); inDegree[v]++; }

  const queue = [];
  for (let i = 0; i < n; i++) if (inDegree[i] === 0) queue.push(i);

  const order = [];
  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    for (const neighbor of adj[node]) {
      if (--inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  // אם order.length < n - יש מחזור בגרף!
  return order.length === n ? order : [];
}

אלגוריתם 2 - DFS עם מחסנית

מריצים DFS ובסיום ביקור כל צומת (post-order) דוחפים אותו למחסנית. בסוף, הפיכת המחסנית נותנת את הסדר הטופולוגי.

function topoSortDFS(n, edges) {
  const adj = Array.from({length: n}, () => []);
  for (const [u, v] of edges) adj[u].push(v);

  const visited = new Array(n).fill(0); // 0=לא, 1=בתהליך, 2=סיים
  const stack = [];
  let hasCycle = false;

  function dfs(u) {
    visited[u] = 1;
    for (const v of adj[u]) {
      if (visited[v] === 1) { hasCycle = true; return; } // מחזור!
      if (visited[v] === 0) dfs(v);
    }
    visited[u] = 2;
    stack.push(u);
  }

  for (let i = 0; i < n; i++) if (visited[i] === 0) dfs(i);
  return hasCycle ? [] : stack.reverse();
}

השוואה בין שני האלגוריתמים

שאלות ראיון נפוצות

• Course Schedule (LeetCode 207) - האם ניתן לסיים את כל הקורסים? (זיהוי מחזור)
• Course Schedule II (LeetCode 210) - מה סדר הקורסים? (Topological Sort)
• Alien Dictionary - מציאת סדר האותיות בשפה זרה מרשימת מילים
• Task Scheduler - תזמון משימות עם תלויות