Key Concepts

Review core concepts you need to learn to master this subject

Depth-First Search Complexity

DFS has time and space complexity of O(n).

Breadth-First Search: Python
Lesson 1 of 2
  1. 1
    The breadth-first search is a tree traversal algorithm that searches a tree level by level. The search starts with the root node and works its way through every sibling node on a level before movin…
  2. 2
    There are many real-world examples that can be represented by the tree data structure. For example, locations on a map can be represented by a tree, where the children of a location node are locati…
  3. 3
    Initializing the search function is the first step to the main algorithm. The parameter of the function should include the following two pieces of data needed to perform the search: - the root nod…
  4. 4
    With the function created, we will now start the algorithm by initializing the frontier queue. In this implementation, the frontier queue is called path_queue and will hold a list for each node tha…
  5. 5
    The heart of the algorithm is the loop that contains the search process. The first half of this process is: Pop the next path list off the frontier Get the frontier node from the path list Check if…
  6. 6
    Now on to the second half of the search process: For each child of the current node Make a copy of the current path Add the child to the copy Append the updated path to the frontier To ens…
  7. 7
    Congratulations on implementing a breadth-first search algorithm using Python! Let’s go over the steps taken to create a breadth-first search function: - Before starting the search, define the tre…

How you'll master it

Stress-test your knowledge with quizzes that help commit syntax to memory

Pro Logo