26.2.2. Representation of Graphs

Try these first

1. 1.

   What is the primary purpose of an adjacency matrix?

   Hint

   Think about how a table reflects relationships in a graph.

2. 2.

   What does the space complexity O(V + E) pertain to?

   Hint

   Remember it combines both vertices and edges.

3. 3.

   What is the space complexity of an adjacency matrix?

   • O(V)
   • O(V^2)
   • O(V + E)

   Hint

   Consider how many entries the matrix needs.

4. 4.

   True or False: An adjacency list can represent the graph more memory-efficiently for sparse graphs.

   • True
   • False

   Hint

   Think about space usage and how many connections we have.

5. 5.

   Create an adjacency matrix and an adjacency list for a directed graph with 5 vertices and the following edges: (0 -> 1), (0 -> 2), (1 -> 3), (3 -> 4).

   Hint

   Focus on how directed edges affect your representation.

6. 6.

   Explain a scenario where an adjacency list is preferred over an adjacency matrix for representing a graph.

   Hint

   Think about social dynamics in a graph.