23.2.1. Introduction to DAGs

Try these first

1. 1.

   Define a Directed Acyclic Graph (DAG).

   Hint

   Focus on the terms directed and acyclic.

2. 2.

   What does 'in-degree' describe?

   Hint

   Think about the incoming connections to a node.

3. 3.

   What is a key characteristic of a DAG?

   • It has cycles.
   • It is undirected.
   • There are no cycles.
   • It has more than one edge.

   Hint

   Recall the definition of acyclic.

4. 4.

   True or False: A task with in-degree of zero can be started immediately.

   • True
   • False

   Hint

   Think about task dependencies.

5. 5.

   Given the tasks A, B, C, and D with the dependencies A -> B, A -> C, B -> D, C -> D, construct a DAG and describe the sequence of tasks.

   Hint

   Focus on the dependencies to form the correct order.

6. 6.

   If a DAG has three vertices with in-degrees of 0, discuss how this could affect topological sorting.

   Hint

   Consider how having more starting points impacts task sequencing.