Dependency Graphs Examples: 44 Problems with Answers
Worked examples of Dependency Graphs to try before you open each solution, then practice problems with answers.
Worked Examples
Example 1
easyShow solution
Answer
First step
Full solution
- 2. Draw the directed graph: . An arrow from to means must be completed before .
- 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 .
Example 2
mediumExample 3
mediumExample 4
mediumExample 5
mediumExample 6
mediumExample 7
mediumExample 8
hardExample 9
hardExample 10
hardExample 11
challengePractice Problems
Try each one, then open the solution to compare your method.
Example 1
mediumExample 2
hardExample 3
easyExample 4
easyExample 5
easyExample 6
easyExample 7
easyExample 8
easyExample 9
easyExample 10
easyExample 11
mediumExample 12
mediumExample 13
mediumExample 14
mediumExample 15
mediumExample 16
mediumExample 17
mediumExample 18
mediumExample 19
mediumExample 20
challengeExample 21
challengeExample 22
challengeExample 23
easyExample 24
easyExample 25
easyExample 26
easyExample 27
mediumExample 28
mediumExample 29
mediumExample 30
mediumExample 31
mediumExample 32
hardExample 33
hardWhat 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.
Ask yourself: Are you mapping which variables directly influence which others with directed arrows?
Concept recap
A dependency graph is a directed graph where nodes are variables and arrows show which variables directly influence which others.
A recipe's prep plan: the sauce needs chopped onions and stock, the stock needs simmered bones, and the plated dish needs the sauce and the pasta. The arrows tell you what to start first and what a late delivery of onions will hold up. Unlike a kitchen plan, a dependency graph says nothing about how long each step takes.
Read the full lesson on Dependency GraphsRelated concepts
Background knowledge
These ideas may be useful before you work through the harder examples.