Revisiting BFS and DFS for graphs
We have already seen how we can implement a breadth first search (BFS) and a depth first search (DFS) in a tree structure. We will revisit our BFS and DFS for graphs. The difference between a tree implementation and a graph implementation is that in a graph implementation, we can start from any vertex, whereas we start from the root of the tree in a tree data structure. Another important thing to consider is that our graphs can have cycles, which were absent in the tree, so, we cannot revisit a node or vertex as it will end up in an infinite loop. We will use a concept called graph coloring where we keep the status of different node visits with a color or a value to keep it simple. Let's now write some code to implement the BFS and DFS in the graph.
Breadth first search
We are now going to implement a BFS for a graph. Considering the following undirected graph, first, we need to represent the graph in a matrix or list. For the sake of simplicity, we will use...