20.2.2. Adjacency List

Try these first

1. 1.

   What does a graph consist of?

   Hint

   Think about network connections.

2. 2.

   Describe an adjacency list.

   Hint

   Consider how you would list friends for each person.

3. 3.

   What does BFS explore?

   • All vertices at once
   • Level by level
   • Randomly

   Hint

   Think about how we explore new buildings in a neighborhood.

4. 4.

   Using an adjacency list reduces the time complexity of BFS to which of the following?

   • O(n²)
   • O(n + m)
   • O(m²)

   Hint

   Focus on how the graph structure affects algorithm performance.

5. 5.

   Given the following graph with 6 vertices represented as an adjacency list {1: [2, 3], 2: [1, 4], 3: [1], 4: [2, 5, 6], 5: [4], 6: [4]}, implement BFS starting from vertex 1. Provide the order of visited vertices and their levels.

   Hint

   Track your progress with a queue and level records.

6. 6.

   Consider a graph where you need to compute the shortest path from vertex A to vertex D. Describe how you would implement BFS to find this path.

   Hint

   Think about the relationships between vertices as you explore.