25.1.2. Topological Sorting

Try these first

1. 1.

   What characterizes a Directed Acyclic Graph (DAG)?

   Hint

   Think about the definition of a cycle.

2. 2.

   What is meant by topological sorting?

   Hint

   Consider how you would organize tasks with dependencies.

3. 3.

   What is a Directed Acyclic Graph?

   • A graph with cycles
   • A graph with no cycles
   • A graph with undirected edges

   Hint

   Consider the definition of a cycle in any graph.

4. 4.

   True or False: A topological sort can be applied to any directed graph.

   • True
   • False

   Hint

   Remember the condition of acyclic property.

5. 5.

   Given a DAG representing a project management scenario, with tasks and their dependencies, derive the longest path and the minimum time required to complete all tasks if task durations are known.

   Hint

   Break down the problem into manageable parts by depicting the graph first.

6. 6.

   Design an algorithm that efficiently computes the longest path in a graph given its adjacency list. Can you implement this in Python?

   Hint

   Recall the steps we discussed regarding topological sorting and path calculation.