24.1. Topological Ordering of Directed Acyclic Graphs (DAG)

Try these first

1. 1.

   What is the in-degree of a vertex?

   Hint

   Think about how many arrows point to the vertex.

2. 2.

   What type of graph is necessary for topological sorting?

   Hint

   Remember the acronym DAG!

3. 3.

   What does 'in-degree' refer to in a directed graph?

   • Count of outgoing edges
   • Count of incoming edges
   • Total edges

   Hint

   Think about the arrows pointing towards the vertex.

4. 4.

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

   • True
   • False

   Hint

   Consider the definition of a DAG.

5. 5.

   Given a DAG with vertices A, B, C, and edges A->B, A->C, B->C, what is a possible topological order?

   Hint

   Focus on the dependencies before drawing the order.

6. 6.

   If a vertex D has an in-degree of 2 and is eliminated, how would that affect the graph?

   Hint

   Think about how dependencies work.