19.1.1. Graph Basics

Try these first

1. 1.

   What is a vertex in a graph?

   Hint

   Think about what elements make up a graph.

2. 2.

   Define an undirected edge.

   Hint

   Consider how you would represent a two-way street in a city.

3. 3.

   What does an adjacency matrix represent?

   • A 1D array
   • A list of neighbors
   • A 2D array of edges

   Hint

   Think about how you visualize a grid.

4. 4.

   True or False: An undirected edge has a direction.

   • True
   • False

   Hint

   Consider the meaning of undirected.

5. 5.

   Construct a graph using an adjacency matrix for five vertices where vertex 1 is connected to vertices 2 and 3, vertex 2 to vertex 4, and vertex 3 to vertex 5. Show your work.

   Hint

   Remember to mark both directions for undirected edges.

6. 6.

   Using breadth-first search, describe how you would traverse this constructed graph from vertex 1 to determine all reachable vertices.

   Hint

   Remember to keep track of the visited vertices and the order you explore.