Dependency Graph

return the correct order to execute tasks so that the target can run.

Task Execution Order (Dependency Resolution)

Problem

You have a set of tasks. Each task has dependencies, which are tasks that must run before it.

Given the dependencies and a target task, return the correct order to execute tasks so that the target can run.

A → {B, C}
B → {E}
C → {D, E, F}
D → {F}
E → {}
F → {B}

• A → {B, C} means A needs B and C to finish first.
• E → {} means E has no dependencies.

Example

Input: graph above, target = "A"
Output: E → B → F → D → C → A

• E has no dependencies, so it can run first.
• B needs only E, so it runs next.
• F needs only B, so it runs next.
• D needs F, and C needs D, E and F.
• A needs B and C, so it runs last.

Note: More than one valid order can exist. Any order where every task comes after all of its dependencies is correct.

Main Idea

This is a topological sort problem. We can solve it in two ways:

• DFS (post-order): Go deep into the dependencies first, and add a task after all its dependencies.
• Kahn's algorithm (BFS): Repeatedly run the tasks that have no remaining dependencies.

Solution 1: DFS with Post-Order

The rule is simple: before we add a task to the answer, we must first add all of its dependencies.

We track each task with two sets:

• visited: The task is fully processed and already in order.
• inProgress: The task is on the current DFS path. If we reach it again, there is a cycle.

function executionOrder(graph, target) {
  const visited = new Set();    // fully processed
  const inProgress = new Set(); // on the current DFS path (for cycle detection)
  const order = [];

  function visit(task) {
    // already done, nothing to do
    if (visited.has(task)) return;

    // we came back to a task on the current path, so there is a cycle
    if (inProgress.has(task)) {
      throw new Error(`Cycle detected at task "${task}"`);
    }

    inProgress.add(task);

    // run dependencies first
    for (const dep of graph[task] || []) {
      visit(dep);
    }

    inProgress.delete(task);

    visited.add(task);
    order.push(task); // post-order: added after all its dependencies
  }

  visit(target);
  return order;
}

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

console.log(executionOrder(graph, "A").join(" → "));
// E → B → F → D → C → A

How the Code Works

• visit(task) returns right away if the task is in visited.
• If the task is in inProgress, we found a cycle, so we throw an error.
• Otherwise, we mark it inProgress, visit every dependency, then move it to visited and push it to order.
• graph[task] || [] gives an empty list if the task is not in the graph, so the code does not crash.
• visit(target) starts the DFS. Only tasks the target needs are added.

Dry Run

Complexity

• Time Complexity: O(V + E)
  • V is the number of tasks and E is the number of dependency links.
  • Each task is processed once, and each link is checked once.
• Space Complexity: O(V)
  • visited, inProgress and order each hold at most V tasks.
  • The recursion stack can go as deep as V in a long chain.

Solution 2: Kahn's Algorithm (BFS)

Kahn's algorithm does not use recursion. It works like this:

• A task can run only when all of its dependencies are done.
• So we count, for each task, how many dependencies are still waiting. This count is called the in-degree.
• A task with in-degree 0 is ready to run.
• When a task finishes, every task that depends on it has one less waiting dependency.
• If that count becomes 0, the task is ready, so we add it to the queue.

What is different in this problem

Kahn's algorithm normally sorts the whole graph. Here, we want only the tasks that the target needs. So we have two extra parts:

• Find the needed tasks: Start from the target and collect every task it depends on, directly or indirectly. Other tasks are ignored.
• Build a reverse map: The graph tells us "task → its dependencies". Kahn's algorithm also needs "task → tasks that depend on it". We call this map dependents.

For our example, the reverse map looks like this:

E → {B, C}     (B and C need E)
B → {A, F}
F → {C, D}
D → {C}
C → {A}
A → {}

Code

function executionOrderKahn(graph, target) {
  // Step 1: find all tasks that the target needs
  const needed = new Set([target]);
  const stack = [target];

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

    for (const dep of graph[task] || []) {
      if (!needed.has(dep)) {
        needed.add(dep);
        stack.push(dep);
      }
    }
  }

  // Step 2: build in-degree and dependents
  const indegree = new Map();   // task -> number of dependencies waiting
  const dependents = new Map(); // task -> tasks that depend on it

  for (const task of needed) {
    indegree.set(task, 0);
    dependents.set(task, []);
  }

  for (const task of needed) {
    // Set removes duplicate dependencies, so we do not count one twice
    for (const dep of new Set(graph[task] || [])) {
      indegree.set(task, indegree.get(task) + 1);
      dependents.get(dep).push(task);
    }
  }

  // Step 3: start with tasks that have no dependencies
  const queue = [];
  for (const [task, degree] of indegree) {
    if (degree === 0) queue.push(task);
  }

  // Step 4: process the queue
  const order = [];
  let head = 0; // pointer instead of shift(), so each pop is O(1)

  while (head < queue.length) {
    const task = queue[head++];
    order.push(task);

    for (const next of dependents.get(task)) {
      indegree.set(next, indegree.get(next) - 1);

      // all dependencies of "next" are done, so it is ready
      if (indegree.get(next) === 0) {
        queue.push(next);
      }
    }
  }

  // Step 5: if some tasks never became ready, there is a cycle
  if (order.length !== needed.size) {
    throw new Error("Cycle detected");
  }

  return order;
}

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

console.log(executionOrderKahn(graph, "A").join(" → "));
// E → B → F → D → C → A

How the Kahn Code Works

Step 1: Find the needed tasks

• We start from the target and walk through its dependencies with a stack.
• needed holds every task the target needs, including the target itself.
• The check !needed.has(dep) stops us from adding a task twice.

Step 2: Build in-degree and dependents

• indegree.get(task) is the number of dependencies that task has.
• For each dependency dep of task, we do two things:
  • Add 1 to the in-degree of task.
  • Add task to dependents.get(dep), so that when dep finishes, we know whom to update.
• new Set(...) removes duplicates. Without it, a repeated dependency would be counted twice, and the task would never reach 0 correctly.

Step 3: Fill the queue with ready tasks

• Every task with in-degree 0 has no dependencies, so it can run first.
• In our example, only E is ready at the start.

Step 4: Process the queue

• Take a task from the front of the queue and add it to order.
• For every task that depends on it, reduce the in-degree by 1.
• When an in-degree becomes 0, all of that task's dependencies are done, so we add it to the queue.
• We use a head pointer instead of queue.shift(), because shift() can take O(n) time.

Step 5: Check for a cycle

• In a cycle, each task waits for another task in the cycle, so none of them reaches in-degree 0.
• Then order has fewer tasks than needed, so we throw an error.

Dry Run of Kahn's Algorithm

In-degrees at the start (the number of dependencies of each task):

The queue starts as [E], because only E has in-degree 0.

order has 6 tasks, and needed has 6 tasks. So there is no cycle, and the answer is E → B → F → D → C → A.

Cycle Example

const badGraph = {
  A: ["B"],
  B: ["E"],
  E: ["A"],
};

executionOrderKahn(badGraph, "A");
// Error: Cycle detected

• needed = {A, B, E}, and each task has in-degree 1.
• No task has in-degree 0, so the queue starts empty.
• order stays empty, which is less than needed.size (3). So we throw an error.

Complexity

• Time Complexity: O(V + E)
  • V is the number of needed tasks and E is the number of dependency links between them.
  • Finding the needed tasks, building the maps and processing the queue each take O(V + E).
• Space Complexity: O(V + E)
  • needed, indegree and queue hold up to V tasks.
  • dependents stores one entry for each dependency link, which is E.

DFS vs Kahn's Algorithm

Note: Both give a valid order, but they may give different valid orders on other graphs. For this example, both give E → B → F → D → C → A.

Summary

• This is a topological sort: every task must come after all of its dependencies.
• DFS adds a task to order only after its dependencies. It uses inProgress to find cycles.
• Kahn's algorithm runs the tasks whose in-degree is 0. After a task runs, it lowers the in-degree of the tasks that depend on it.
• For a single target, first collect only the tasks the target needs, and then build the in-degree and dependents maps.
• In Kahn's algorithm, a cycle means some tasks never reach in-degree 0, so order is shorter than needed.
• Use a head pointer instead of shift() to keep the queue fast.
• Use Kahn's algorithm when the dependency chain is very long, because it has no recursion.
• Both solutions run in O(V + E) time.