23.2.2. Dependency Problem Description

Try these first

1. 1.

   What is a Directed Acyclic Graph (DAG)?

   Hint

   Think of the meaning of 'Acyclic'.

2. 2.

   What do we understand by in-degree of a vertex?

   Hint

   Consider incoming arrows.

3. 3.

   What is the key feature of a Directed Acyclic Graph (DAG)?

   • Contains cycles
   • Has directed edges with a cycle
   • Has no cycles

   Hint

   Focus on the definition of 'Acyclic'.

4. 4.

   True or False? Topological sorting is possible for graphs with cycles.

   • True
   • False

   Hint

   Consider the implications of a cycle.

5. 5.

   You are given a set of tasks with cyclic dependencies (A -> B, B -> C, C -> A). Explain why a topological sort cannot be performed.

   Hint

   Reflect on circular dependencies.

6. 6.

   For a DAG consisting of tasks A, B, C, and dependencies A -> B, A -> C, C -> D, determine a possible valid topological order.

   Hint

   Think about which tasks can be completed first based on their dependencies.