How to walk a graph

Walking a graph is as simple as visiting each node and doing some operations for it. There are mainly two ways of walking (or traversing) a graph:

1. BFS (Breadth First Search)
2. DFS (Depth First Search)

Alright! Let’s do it. Let us take an example.

Your mom has given you a grocery list and the exact shops you need to buy them from.

You are a nerd (like me) and do not have good knowledge of the neighbourhood (or maybe you moved in recently lol). So you take a look at your google maps and figure out the exact locations of the stores you need to visit.

However, you are a nerd, remember ? You wanna know how many blocks of stores you have to visit. For example, if in the following list, 1s represent the location of the stores you need to visit, then there are 2 blocks that you want to visit.

1 1 1 1 0 0 0
1 1 1 0 0 0 0
1 1 0 0 0 1 1
1 1 0 0 0 1 1

Now, how do you calculate this ?

In real life, it’s easy to calculate as we will just draw a boundary across the ones and say there are two blocks. But how do you do this in code ? Let’s see that down below.

BFS (Breadth First Search)

So this is one approach that you can take. Here, you visit each element (node) and then, plan where you want to visit next. So, we start from (0, 0) and then we want to visit (0, 1) and (1, 0). Notice that both of these are having ones, hence, we can visit them. Next, we visit (0, 1) and we plan on visiting the adjacent elements, which are 1, i.e., (0, 2) and (1, 1). Notice how we are not going for (0, 0) again even though it’s adjacent as we’ve already visited it (also, nerds are lazy so).

So we continue to visit the elements this way, in layers and we visit each element exactly once.

Now, let’s convert this to code.

We maintain a queue for each block (component) we visit. We also maintain a visited array where we can mark the elements we’ve already visited as true.

Initially, when we are visiting a block (component), we add the first node (or the root node for the component) into the queue. Also, we need to keep a note that we have already visited this element (node), so, we mark the index of this node in the visited array as true.

Then we start traversing the block(component) and for each iteration, we first pop the first element in the queue and push the adjacent elements (nodes) of this element into the queue.

Once we are done, we can end the function call and go for the next block(component).

Now, time for some nerdy content. Let’s talk about the time and space complexity of this algorithm.

Time Complexity: O(N+E)
Space Complexity: O(N)
N = Number of nodes in the graph
E = Number of edges in the graph

With that, you’ve successfully calculated the number of blocks you need to go to. Make sure you go back home safely along with the groceries or your mom will be mad and send you back for shopping.

DFS (Depth First Search)

This is approach that you can take. Here, you visit each element (node) and then, go to the immediate next element (node) that you see. So if you visit (0, 0), you go to (0, 1) next, then (0, 2) and so on until you see an element with no store (node with 0 value).

So we continue to visit the elements this way, in order and we visit each element exactly once.

Now, let’s convert this to code.

We can make a recursive function that takes in the current element (node) and marks it as visited (same way as in BFS, but without a queue). Then, it makes a recursive call to the same function with the immediate neighbours of this element (node) only if it has not been visited already.

Another way to do this is using a stack that can effectively simulate the recursion call stack. However, this is more efficient sometimes (when the number of nodes are more).

Now, it’s again time for some nerdy content. Let’s talk about the time and space complexity of this algorithm as well.

Time Complexity: O(N+E)
Space Complexity: O(N)
N = Number of nodes in the graph a
E = Number of edges in the graph

With that, you’ve successfully calculated the number of blocks you need to go to again. Make sure that this time, you go back home safely along with the groceries or your mom will be really mad and maybe cut you computer power ot wifi line.

With that said, Thanks for reading it till the end! If you want some more of these graph blogs, stay tuned as I’m gonna write a lot of em from now on.