Get startedGet started for free

Breadth First Search (BFS)

1. Breadth First Search (BFS)

In this video, we will explore the breadth first search algorithm in binary trees and graphs.

2. Breadth first search - binary trees

Breadth first search starts from the root and visits every node of every tree level before going on to the next level.

3. Breadth first search - binary trees

Let's look at an implementation in code. In this case, we will not make use of recursion, but as we will see, we will use a queue. If the tree has a root, we create an empty list to keep track of the nodes we visit. We also create a queue to store the nodes to be visited

4. Breadth first search - binary trees

and add the root to it. Note that in this case, we use Python's SimpleQueue. We start a loop that will run until the queue is empty, doing the following.

5. Breadth first search - binary trees

We remove the first vertex from the queue, assign it to the current_node variable,

6. Breadth first search - binary trees

and append it to the visited_nodes list. If current_node has a left child,

7. Breadth first search - binary trees

we add it to the queue, and do the same

8. Breadth first search - binary trees

if it has a right child.

9. Breadth first search - binary trees

We keep

10. Breadth first search - binary trees

iterating

11. Breadth first search - binary trees

until

12. Breadth first search - binary trees

the queue

13. Breadth first search - binary trees

is empty,

14. Breadth first search - binary trees

meaning

15. Breadth first search - binary trees

that all

16. Breadth first search - binary trees

the nodes

17. Breadth first search - binary trees

in the

18. Breadth first search - binary trees

binary

19. Breadth first search - binary trees

tree

20. Breadth first search - binary trees

have

21. Breadth first search - binary trees

been

22. Breadth first search - binary trees

visited.

23. Breadth first search - binary trees

Finally, we return the visited_vertices list. The complexity is O of n, where n is the number of nodes.

24. Breadth first search - graphs

The breadth first search algorithm applied to graphs is quite similar, but as graphs can have cycles, we need to check if the vertices have already been visited.

25. Breadth first search - graphs

As in the binary tree version, we create an empty list to keep track of the vertices we visit and create the queue. This time, we add to the queue the vertex we propose as initial_vertex and append it to the list of visited_vertices. We start a loop that will run until the queue is empty, doing the following. We remove the first vertex from the queue and assign it to the current_vertex variable. Then, we iterate all the adjacent vertices of the current_vertex, and for each of them, we check if it has already been visited. If it hasn't, we append it to the visited_vertices list and add it to the queue. We keep iterating until we finish the algorithm, and finally, we return the visited_vertices list. The complexity of this algorithm is O of V plus E, where V is the number of vertices, and E is the number of edges.

26. Breadth first search - graphs

Let's see this algorithm in action. As we can see, the visited nodes list keeps track of all the vertices we visit. Notice that if a vertex has already been visited, we don't add it to the visited nodes list.

27. BFS vs DFS

Depending on the scenario, one of the two algorithms will be more applicable than the other. If our target is close to the starting vertex, breadth first search will be more applicable. Some applications of breadth first search are web crawling, finding the shortest path in unweighted graphs, finding all the connected locations of a particular location using GPS, etc. If our target is far away from the starting vertex, depth first search will be more applicable. Some applications of depth first search are solving puzzles with only one solution, like for example, mazes, detecting cycles in graphs, finding the shortest path in a weighted graph, etc. Finally, both of them are used as part of other more complex algorithms.

28. Let's practice!

Let's practice with the breadth first search!