Dependency Graphs Examples: 44 Problems with Answers

Start with the recap, study the fully worked examples, then use the practice problems to check your understanding of Dependency Graphs.

This page combines explanation, solved examples, and follow-up practice so you can move from recognition to confident problem-solving in Math.

Concept Recap

A dependency graph is a directed graph where nodes are variables and arrows show which variables directly influence which others.

Like a flowchart: A affects B, B affects C. Arrows show dependencies.

Read the full concept explanation →

How to Use These Examples

Read the first worked example with the solution open so the structure is clear.
Try the practice problems before revealing each solution.
Use the related concepts and background knowledge badges if you feel stuck.

What to Focus On

Core idea: A dependency graph draws each variable as a node with arrows showing which variables directly drive which others.

Common stuck point: The procedure for dependency graphs is the easy part; the trap is drawing the arrow toward the variable that's known first. Asking "Are you mapping which variables directly influence which others with directed arrows?" first is what keeps a correct-looking calculation from being attached to the wrong concept.

Sense of Study hint: Ask: Are you mapping which variables directly influence which others with directed arrows?

Worked Examples

Example 1

easy

Three tasks have the following dependencies: Task B depends on Task A, and Task C depends on Task B. Draw the dependency graph and determine a valid execution order.

Answer

A \to B \to C

First step

Identify the dependencies:

A \to B

(B depends on A) and

B \to C

(C depends on B).

Full solution

2
Draw the directed graph: $A \to B \to C$ . An arrow from $X$ to $Y$ means $X$ must be completed before $Y$ .
3
Perform a topological sort: start with the node that has no incoming edges (A), then B, then C.
4
The valid execution order is $A, B, C$ .

A dependency graph is a directed acyclic graph (DAG) where edges represent prerequisite relationships. A topological sort gives a valid ordering that respects all dependencies, ensuring no task is started before its prerequisites are complete.

Example 2

medium

Given the dependencies:

D

depends on

A

and

B

;

E

depends on

B

and

C

;

F

depends on

D

and

E

. Find all valid topological orderings.

Example 3

medium

Tasks

A \to B

A \to C

B \to D

C \to D

. What is the minimum number of stages to complete all tasks if independent tasks can run in parallel?

Example 4

medium

Given

A \to B

A \to C

B \to D

C \to D

D \to E

, list one valid topological order.

Example 5

medium

In the DAG with edges

A \to B

A \to C

B \to D

C \to D

D \to E

, what is the longest path length (in edges) from

A

E

Example 6

medium

How many distinct topological orderings does the DAG

A \to B

A \to C

have? (No other edges.)

Example 7

medium

Tasks

A, B, C, D, E, F

with dependencies

A \to C

B \to C

C \to D

C \to E

D \to F

E \to F

. What is the minimum number of parallel stages needed?

Example 8

hard

Given the DAG with edges

A \to B

A \to C

B \to D

C \to D

, count all distinct topological orderings.

Example 9

hard

Add the edge

D \to A

to the DAG with edges

A \to B

B \to C

C \to D

. Does a topological order still exist?

Example 10

hard

A dependency graph has

n

nodes arranged as a chain

v_1 \to v_2 \to \cdots \to v_n

. How many distinct topological orderings are there?

Example 11

challenge

In the DAG

A \to B

A \to C

B \to D

C \to D

A \to E

D \to E

, count all distinct topological orderings.

Practice Problems

Try these problems on your own first, then open the solution to compare your method.

Example 1

medium

A project has tasks with dependencies:

B

depends on

A

;

C

depends on

A

;

D

depends on

B

and

C

. What is the minimum number of time steps needed if independent tasks can run in parallel?

Example 2

hard

Given the dependency graph with edges

A \to C

A \to D

B \to D

B \to E

C \to F

D \to F

E \to F

, determine whether adding the edge

F \to A

would create a problem, and explain why.

Example 3

easy

In a dependency graph, an arrow goes from

A

B

. Which variable depends on which?

Example 4

easy

In the chain

A \to B \to C

, does changing

A

affect

C

Example 5

easy

A formula computes

C = A + B

. Draw the dependency arrows.

Example 6

easy

A

depends on

B

and

B

depends on

A

, what kind of structure is this?

Example 7

easy

A \to C

and

B \to C

, how many variables directly affect

C

Example 8

easy

Two variables

A

and

B

are correlated but neither causes the other; both depend on

C

. Draw the arrows.

Example 9

easy

Does correlation between

A

and

B

guarantee that one depends on the other? Answer yes or no.

Example 10

easy

In a dependency graph, what does it mean if a node has no incoming arrows?

Example 11

medium

Given

D = A + B

and

E = D \cdot C

, list every variable that

E

depends on, directly or indirectly.

Example 12

medium

In a spreadsheet, cell

C1 = A1 + B1

and

D1 = C1 \cdot 2

. If

A1

changes, which cells must be recomputed?

Example 13

medium

A graph has arrows

A \to B

B \to C

C \to A

. Can the variables be evaluated in a fixed order? Explain.

Example 14

medium

Find a valid evaluation order for

C = A + B

E = C + D

, where

A, B, D

are inputs.

Example 15

medium

In the graph

A \to B

A \to C

B \to D

C \to D

, what is the in-degree of

D

Example 16

medium

Variables: rainfall

\to

soil moisture

\to

crop yield, and temperature

\to

crop yield. If only temperature changes, does soil moisture change?

Example 17

medium

Why is reading an arrow backwards a serious error in a dependency graph?

Example 18

medium

In the graph

A \to B

A \to C

B \to D

C \to D

, what is the out-degree of

A

Example 19

medium

Given

C = A \cdot B

and

E = C + A

, which inputs does

E

depend on?

Example 20

challenge

A system has

A \to B

A \to C

B \to D

C \to D

D \to E

. If

A

changes, list all affected variables and give one valid recomputation order.

Example 21

challenge

Two researchers see that ice-cream sales and drowning rates rise together. Model this with a dependency graph and explain why neither causes the other.

Example 22

challenge

A graph claims

A \to B

B \to C

C \to A

is a valid computation pipeline. Identify the flaw and state the condition needed to fix it.

Example 23

easy

In a dependency graph, the edge

X \to Y

means which variable directly influences the other?

Example 24

easy

A formula computes

V = IR

. Draw the dependency arrows from inputs to output.

Example 25

easy

A graph has edges

A \to B

A \to C

B \to D

. List the parents of

D

Example 26

easy

For

z = f(x) + g(y)

, draw the dependency graph and identify the leaf node.

Example 27

medium

A spreadsheet has cells

B1 = A1 + 2

C1 = B1 \cdot 3

D1 = A1 + C1

. List the recompute order if

A1

changes.

Example 28

medium

Tasks:

A \to C

B \to C

C \to D

C \to E

. How many tasks have

C

as a direct prerequisite?

Example 29

medium

A function machine has

u = x + y

v = u \cdot z

w = v + u

. List the edges of its dependency graph.

Example 30

medium

In a dependency graph, can the same variable appear as both an ancestor and a descendant of another? Answer with justification.

Example 31

medium

A model has

X \to Y

Z \to Y

Y \to W

. Which variables does

W

depend on (directly or indirectly)?

Example 32

hard

A build system has files with edges

\text{src}_1 \to \text{obj}_1

\text{src}_2 \to \text{obj}_2

\text{obj}_1 \to \text{exe}

\text{obj}_2 \to \text{exe}

. If

\text{src}_1

changes, which targets need rebuilding?

Example 33

hard

A research workflow has

X \to Y

X \to Z

Y \to W

Z \to W

. If

X

and

W

are observed but

Y

and

Z

are hidden, can we still infer the value of

W

when

X

changes?

← Back to Dependency Graphs Practice Mode

Related Concepts

Functional Dependency

Background Knowledge

These ideas may be useful before you work through the harder examples.

functional dependency