19.1.5. Algorithm Strategies

Try these first

1. 1.

   Define a vertex in a graph.

   Hint

   Think of the graph as a collection of points.

2. 2.

   What does an undirected edge represent?

   Hint

   Consider how you'd connect cities in a map.

3. 3.

   What does an adjacency matrix represent?

   • A list of edges
   • A 2D array of vertex connections
   • A tree structure

   Hint

   It is a structured way of showing connections.

4. 4.

   True or False: BFS explores as deep as possible before backtracking.

   • True
   • False

   Hint

   Think about level versus depth.

5. 5.

   Given a graph represented by an adjacency matrix, write a function to determine if there is a path between two vertices.

   Hint

   Focus on exploring each edge systematically.

6. 6.

   Design an efficient algorithm using an adjacency list to find all connected components in an undirected graph.

   Hint

   Each time you start a new DFS/BFS from an unvisited vertex, you've found a new component!