19.1.6. Adjacency List Representation

Try these first

1. 1.

   What does a vertex represent in a graph?

   Hint

   Think about the dots in a graph.

2. 2.

   How does an adjacency matrix represent a graph?

   Hint

   Remember the rows and columns represent vertices.

3. 3.

   What is the main advantage of an adjacency list?

   • Faster access to all vertices
   • Space-efficient for sparse graphs
   • Easy to implement

   Hint

   Think about how many edges there are in a sparse graph.

4. 4.

   True or False: An adjacency matrix can easily represent the absence of edges.

   • True
   • False

   Hint

   Consider what happens in a sparse graph.

5. 5.

   Consider a directed graph represented by an adjacency list. How many different edges can the graph contain if you have 'n' vertices? Provide a general formula and an example.

   Hint

   Think about how many unique connections can exist.

6. 6.

   Given a sparse graph represented using an adjacency list, describe the impact on time complexity when attempting to find all neighbors of a node versus using a dense graph with an adjacency matrix.

   Hint

   Consider how many edges relative to nodes influence the retrieval processes.