24.1.6. Using Adjacency List

Try these first

1. 1.

   What is the in-degree of a vertex with no incoming edges?

   Hint

   Think about the definition of in-degree.

2. 2.

   How can we represent a DAG using an adjacency list?

   Hint

   Visualize the connections between vertices.

3. 3.

   What does in-degree indicate for a vertex?

   • Number of outgoing edges
   • Number of incoming edges
   • Total connections

   Hint

   Think about where the edges are coming from.

4. 4.

   True or False: In a DAG, a vertex may have a cycle.

   • True
   • False

   Hint

   Recall the properties of a DAG.

5. 5.

   Create an adjacency list and calculate the in-degrees for a graph described by the edges: A -> B, A -> C, B -> C, B -> D, C -> E.

   Hint

   Start by visualizing how each vertex connects.

6. 6.

   Given a list of tasks and prerequisites, outline the steps to achieve a topological sort and provide the order of task completion.

   Hint

   Keep track of tasks with no remaining prerequisites.