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!