25.1.1. Introduction to DAGs

Try these first

1. 1.

   What is a DAG?

   Hint

   Think about how edges connect vertices and the absence of cycles.

2. 2.

   What does topological sorting help us achieve?

   Hint

   Think about the order of tasks based on prerequisites.

3. 3.

   What is a Directed Acyclic Graph?

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

   Hint

   Focus on the term 'Acyclic'.

4. 4.

   True or False: A topological sort only exists for cyclic graphs.

   • True
   • False

   Hint

   Think of the definition of a topological sort.

5. 5.

   Given a DAG representing a simplified project plan with tasks as vertices (A, B, C, D) and dependencies (A -> B, A -> C, B -> D, C -> D), calculate the longest path. What implications does this have for project scheduling?

   Hint

   Visualize the tasks and dependencies.

6. 6.

   If a graph has vertices with both indegrees and outdegrees, how would you adjust the approach to find the longest path compared to a typical DAG?

   Hint

   Consider what happens if you can revisit vertices.