BFS and DFS Algorithms For Visual Learners

Throughout history, humans have been searching for something. Search made us who we are today. In ancient times, foragers used to search for the essential things to live. They created some tools to make this search easier. The human brain also evolved in this process. Now it could create a mental map of the territory and foragers could map the regions into their own mind and search more efficiently. Even in modern times, we are basically using the same strategy we used before. But now, we have more advanced tools and our minds have evolved more. We use maps to find the way, tools like google maps are the best example of how we have developed ourselves to search more efficiently. BFS and DFS algorithms are just tip of iceberg.

So let’s start, We will take a real-life example to understand the evolution of the search itself.

My Imaginary Girlfriend

So, apparently, I have a girlfriend, Lisa (at least in my imagination). She’s smart and extremely picky about all the things she uses. The other day, she lost her lipstick somewhere. It was her favorite shade. Like I said, she’s extremely picky; she won’t settle for another shade or any other brand. But the problem is that the lipstick is extremely rare, and she’s freaked out. Now, she’s planning to buy a new one. Stores near us are very generous; they will guide her to other stores if they don’t have it. There are a few ways she can start her search; let’s understand them one by one.

Breadth First Search (BFS)

Lisa is an organised girl. Also, knows some beauty shops near her house. She lists down their names on a paper. Let’s say there is some shop A, shop B and shop C. She will enter the names of shops on the list and will visit one by one in a sequential order from top to bottom, starting with shop A. Alas!, shop A don’t have that shade but they suggested her other shops where they might have it.

She listed down those names as Shop D and Shop E. She will follow the list. Next stop, Shop B. Again they don’t have it but they suggested her some other shops. She listed them as well, Shop F and Shop G. Next, Shop C. Now she went to Shop C. They don’t have it either but they couldn’t suggest any shops to her. In the end Lisa’s list looks like this.

In the next step, she is going visit the Shop D which was suggested by Shop A’s owner. If they don’t have it they will suggest her some other shops too. She will add these shops in the list and continue visiting the shops one by one in a sequential manner until she finds that damn lipstick. And she got successful. Lisa found it in some shop which was suggested by shop G’s owner. That was Shop J. Let’s draw a map of all these shops she visited. A connection between two shops signifies that particular shop is suggested by the other shop. In formal terms we call this map as a Graph or in this case, a Tree.

BFS in a Nutshell

It was not the easy task but she got her favorite lipstick. You can observe that Lisa went to the shops suggested by the same shop owner in sequential order. We call this approach the Breadth First Search(BFS) algorithm as we search first all the options available that are previously known and add new options to visit down the road. But the problem with this approach is that it can create redundancy. Observe the case of shop K where shop it can be reached from both shop F and G. And both the times she will visit the shop (she’s dumb, I’m gonna breakup with her). The BFS has this rule to visit all the nodes in the way. It doesn’t matter if they have been visited already.

BFS Implementation in Python

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node, end=" ")
            visited.add(node)
            queue.extend(neighbor for neighbor in graph[node] if neighbor not in visited)


graph = {
    'Shop A': ['Shop B', 'Shop C', 'Shop D'],
    'Shop B': ['Shop A', 'Shop E', 'Shop F'],
    'Shop C': ['Shop A', 'Shop G'],
    'Shop D': ['Shop A', 'Shop H', 'Shop I'],
    'Shop E': ['Shop B'],
    'Shop F': ['Shop B'],
    'Shop G': ['Shop C', 'Shop J'],
    'Shop H': ['Shop D'],
    'Shop I': ['Shop D', 'Shop K', 'Shop L'],
    'Shop J': ['Shop G'],
    'Shop K': ['Shop I'],
    'Shop L': ['Shop I']
}

# Starting node for BFS
start_node = 'Shop A'

print("BFS Traversal:")
bfs(graph, start_node)

Depth First Search (DFS)

In our previous approach, Lisa had to visit almost 10 shops to get lipstick. Let’s see if we can make Lisa’s search more efficient. Let’s try another approach.This time Lisa will list down the suggested shops in a different way than before. This time when she will get the suggestion from a certain shop, she will add it to the top of the list. Initial list will have three shops, same as BFS. After visiting shop A, her list would look like this.

She will mark the shops she has visited already. She will follow the same top-down approach. So her next stop would be shop D. She will add shop D and shop E on the top. Shop D’s owner told her to visit the shop I. She went there but couldn’t find lipstick and the shop I’s owner didn’t tell her any other shop. Lisa has visited all the shops above shop E. Now her list looks like this.

This process of going back to the shop A’s suggestion is called Backtracking in formal terms. Shop E’s owner would tell her to go shop J(added on the top of the list) and bingo! She found her favourite lipstick.

Let’s put that graph again.

DFS in a Nutshell

Lisa went in the depth of the search tree instead of going to the shops on the same level. We call this approach the Depth First Search algorithm. You can see in the graph that Lisa has to visit only 5 shops, much less as compared to our BFS approach. So, we can say that our DFS approach is better than BFS. Also, if she would have visited shop K through shop F then she wouldn’t have visited it through shop G. Because she would have marked it already. Hence, there she will not visit the same shop more than once by this approach.

Performing DFS vs BFS

Let’s focus on Lisa’s list. Just by changing the way she enters new entries, she improved her search significantly. We call this list a data structure. A data structure is a way to store data somewhere in the computer memory. In Lisa’s case, she stored it on the paper. But this storing of data is different for BFS and DFS.

Difference between BFS and DFS

In BFS, she added the new elements at the end of her list and followed the list in the top-down approach. The shops that are added newly in her list are visited after the previous ones i.e. First In First Out(FIFO) approach. We call this type of data structure a Queue. It works the same as the queue we make at the airport. The first customer gets the service first. In the queue new elements are added from the back while older elements are removed from the front and this is what Lisa did exactly in BFS.

In DFS, Lisa added new elements at the top of the list. She did not change her top-down order. In this approach, newer elements are visited before the older ones i.e. Last In First Out(LIFO). We call this data structure a Stack. In stack, elements are added from the one end and from that same end they are removed, in Lisa’s case it was the top of her list where she added the new shops and visited the shops sequentially.

DFS Algorithm Implementation in Python

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()

    if start not in visited:
        print(start, end=" ")
        visited.add(start)

        for neighbor in graph[start]:
            dfs(graph, neighbor, visited)


graph = {
    'Shop A': ['Shop B', 'Shop C', 'Shop D'],
    'Shop B': ['Shop A', 'Shop E', 'Shop F'],
    'Shop C': ['Shop A', 'Shop G'],
    'Shop D': ['Shop A', 'Shop H', 'Shop I'],
    'Shop E': ['Shop B'],
    'Shop F': ['Shop B'],
    'Shop G': ['Shop C', 'Shop J'],
    'Shop H': ['Shop D'],
    'Shop I': ['Shop D', 'Shop K', 'Shop L'],
    'Shop J': ['Shop G'],
    'Shop K': ['Shop I'],
    'Shop L': ['Shop I']
}

# Starting node for DFS
start_node_dfs = 'Shop A'

print("DFS Traversal:")
dfs(graph, start_node_dfs)

Conclusion

DFS is a better algorithm than the BFS because of two reasons.

1. It does not create redundancy in the data structure thus it does not visit the same node that has been visited already.
2. It is computationally easier and more efficient than BFS.

Although, there are some problems with our both algorithms. If we have a larger map with thousands of nodes(shops), these algorithms are not efficient to find the target node. Look at the DFS map, if we had shop L as target node, the performance of DFS would not be much significantly better than BFS. While BFS has a problem of searching for all the nodes, DFS can waste its time searching in the wrong direction.

To solve these problems we have much better algorithms such as Heuristic Algorithms that are actually being used in AI systems. But that’s the blog for another day.

Do you have any doubts or suggestions? Please feel free to reach out to me on [email protected] or hit me directly on LinkedIn, Twitter!