26.2.1. Introduction to Graphs

Try these first

1. 1.

   What are the two main components of a graph?

   Hint

   Think about what makes up a graph.

2. 2.

   What is a directed graph?

   Hint

   Consider if the connections have a direction or not.

3. 3.

   What does a directed graph signify?

   • Edges have no direction
   • Edges have direction
   • All edges are weighted

   Hint

   Think about the meaning of direction in a graph.

4. 4.

   An adjacency list is more efficient for which type of graph?

   • Dense graphs
   • Sparse graphs
   • Cyclic graphs

   Hint

   Consider how many edges exist compared to the number of vertices.

5. 5.

   Design a graph to represent a public transportation system. Describe the vertices, edges, and whether they are directed or undirected.

   Hint

   Think about how real transport systems connect locations.

6. 6.

   Explain how you would use BFS to solve a problem in a computer network. What would be the vertices and edges?

   Hint

   Consider what BFS does and how it explores connected nodes.