20.3.7. Input Size in Graphs

Try these first

1. 1.

   What are the two common ways to represent a graph?

   Hint

   Think about how you can organize the vertices and edges.

2. 2.

   What does BFS stand for?

   Hint

   Consider the order in which you explore nodes.

3. 3.

   What data structure is NOT typically used in BFS?

   • Queue
   • Stack
   • Array

   Hint

   Think about how the nodes are accessed.

4. 4.

   True or False: An adjacency list is more efficient than an adjacency matrix for sparse graphs.

   • True
   • False

   Hint

   Consider memory usage.

5. 5.

   Construct a graph with 10 vertices and 15 edges. Run BFS from vertex 1. Document each step detailing which vertices are visited and in what order.

   Hint

   Use a diagram to track your visited nodes and the queue.

6. 6.

   If a graph represents a social network, explain how BFS could help find the shortest connection path between two people.

   Hint

   Think about how relationships connect people within the context of the graph.