24.1.3. Valid Topological Ordering

Try these first

1. 1.

   What is the in-degree of a vertex?

   Hint

   Think about how many edges arrive at a vertex.

2. 2.

   Can a vertex with zero in-degree be processed first in topological sorting?

   Hint

   If no tasks depend on it, it can go first!

3. 3.

   What is the primary goal of topological sorting?

   • To find the shortest path
   • To order vertices respecting dependencies
   • To find cycles in a graph

   Hint

   Think about the purpose of ordering in task management.

4. 4.

   True or False: A graph must be acyclic to perform a topological sort.

   • True
   • False

   Hint

   Remember the nature of cycles and their constraints.

5. 5.

   Design an algorithm to implement topological sorting with an input of edges in a directed graph. What are the expected outcomes?

   Hint

   Think about how you can maintain order while processing.

6. 6.

   Consider a scenario with tasks {A, B, C, D} and dependencies {A->B, A->C, B->D}. What is a possible topological order?

   Hint

   Every time you select a task, ensure no others depend on it that haven't been completed.