Overview

There are many different ways that you can use graphs to solve problems, but two of the main algorithms are focused on how you search through the graph: breadth-first search and depth-first search. Today we’ll consider these two algorithms and their time complexities.

Basic Learning Objectives

Before class, you should be able to:

  • Explain the high-level idea of breadth- and depth-first search
  • Explain the time complexity of both algorithms

Advanced Learning Objectives

After class, you should be able to:

  • Implement breadth- and depth-first search
  • Demonstrate the time complexity of both

Reading

You should read the following

Checks

Submit your answers to Moodle.

Given the following graph and assuming neighbors are processed in numerical order from least to greatest:

Graph

  1. What is the breadth-first traversal of the graph, starting from node 7?
  2. What is the depth-first traversal of the graph, starting from node 7?