24.1.6.1. Implementation Steps

Try these first

1. 1.

   Define in-degree.

   Hint

   Think about how many edges direct towards that vertex.

2. 2.

   What is a DAG?

   Hint

   What does it mean for a graph to have no cycles?

3. 3.

   What does an in-degree represent in a graph?

   • A count of outgoing edges
   • A count of incoming edges
   • The total number of vertices

   Hint

   Think about which direction the edges point.

4. 4.

   Topological sorting can be performed on which type of graph?

   • True
   • False

   Hint

   What characteristics must the graph have?

5. 5.

   Construct a DAG with at least 6 vertices and demonstrate the process of topological sorting.

   Hint

   Think about how to start with nodes that don't depend on others.

6. 6.

   Analyze a given set of courses with prerequisites and construct a DAG. Determine if a topological sort is possible.

   Hint

   Check if any courses lead back to themselves.