23.2. Directed Acyclic Graphs (DAGs)

Try these first

1. 1.

   Define a Directed Acyclic Graph (DAG).

   Hint

   Remember the key property of a DAG.

2. 2.

   What does in-degree and out-degree refer to?

   Hint

   Think of how edges point to or away from a task.

3. 3.

   What is a Directed Acyclic Graph?

   • A graph with cycles
   • A directed graph without cycles
   • A graph with undirected edges

   Hint

   Think about the meaning of acyclic.

4. 4.

   Is it possible to topologically sort a graph with cycles?

   • True
   • False

   Hint

   Consider if you can complete a task if it depends on itself.

5. 5.

   Create a DAG for scheduling a software development project with the following tasks: Design, Code, Test, Deploy. Assume Design must be completed before Code, and Code must be completed before Test. How would you represent this graphically?

   Hint

   Draw the tasks and the dependencies between them.

6. 6.

   Explain how the presence of a cycle affects the workflow in a project management scenario. What strategies can be employed to prevent cycles in task dependencies?

   Hint

   Consider what happens when one task relies on another that also depends back on the first.