23.2.3. Modeling Dependencies with Graphs

Try these first

1. 1.

   Define a Directed Acyclic Graph (DAG).

   Hint

   Think about what cycles in a graph imply.

2. 2.

   What is the purpose of topological sorting?

   Hint

   Consider how tasks would be completed.

3. 3.

   What is true about a Directed Acyclic Graph?

   • True
   • False

   Hint

   Think about what a cycle would mean in terms of task dependencies.

4. 4.

   Which of the following is a requirement for topological sorting?

   • The graph must be directed
   • The graph must be acyclic
   • Both A and B

   Hint

   Consider the importance of direction and cycles.

5. 5.

   Given five tasks with the following dependencies: A -> B, A -> C, B -> D, C -> D. Describe the topological orderings possible.

   Hint

   Look for tasks without incoming edges to start.

6. 6.

   If a new task E is introduced with dependencies: E -> A, how does this affect topological sorting?

   Hint

   Track how each task's position changes.