Wonders of Breadth First Search

Breadth First Search, you beauty!

I was watching the MIT OCW Video about Breadth First Search, with Erik Demaine teaching. I have to say, this guy is awesome.

So what is Breadth First Search(BFS)? It is a graph search algorithm. A graph, is what you say? A graph is, well, like a map. There are vertices, interconnected with each other (or maybe alone) by “edges”.

Think of it like a city. There are intersections of roads. And the length of road between each intersection varies (Obviously). The intersections are vertices and the roads are edges. The lengths are called weights, but its not really related to BFS as we will know soon.

What does BFS do exactly? BFS is a graph search algorithm. What it does is, go through all of the graph vertices exploring all paths possible. Yes. That is it. But this is in fact a very useful thing.

For example BFS can be used to solve a Rubik’s Cube theoretically at least, but it can surely solve a Pocket Cube (2x2) fairly fast using a normal computer. BFS is also used by web crawlers (Google uses a bit modified BFS, if Erik Demaine is to be believed). BFS can also solve shortest path problems in some cases.

When I’m ending this post, I’ll also throw in a BFS example about the game we call “Chopsticks”. Read on!

But first. How can I represent a graph as a data stucture? Now there are two data structures usually used, Adjacency lists and Adjacency Matrices. List is what I find cool. An Adjacency list is basically a dict (HashMap) which has vertices as keys and values are lists of where the vertex leads to. Like if I have a adj. list:

adj = {
"A": ["B", "C"], 
"B": ["C"],
"C": []
}

Then vertex A can lead to Band C, vertex B can lead to C, and so on.

Usually we have to make an adjacency list out of input data, like a maze is given, and we have to make an adjacency list out of it and then run BFS or any graph related algorithm.Now lets get into the actual algorithm.

Here is the basic outline of what BFS does, I’ll throw in a code example afterwards.

1. Get hold of a starting point. Usually we know which vertex to start the journey from. Let’s call it A. We can reach this vertex in 0 steps.
2. Now let’s make a list of where we can go from this vertex. We can go from A to B and A to C, says the adjacency list. Good then. We can reach these vertices in 1 step. Now next iterations I’ll try going to B and then C. Let’s add them to a list called “next”.
3. Now I will loop through “next” and look at each vertex. next[0] is “B”. Where can I go from “B”? adj list says “C”. Let’s pay “C” a visit next iteration, add it to a list “next2”. Note here we did not check if we have visited it before or it is in next already or not. Because we want to explore all paths, not only all vertices.
4. next[1] is “C”. And the graph ends at “C”. No where to go, nothing to add to “next2”.
5. Let’s see what we have in next2. These vertices can be reached in 3 steps as well. “C” again ends the search. So we are done.

That is the basic outline. We list the places we go next time, and then visit them and keep doing this until we are out of places to go. It’s called Breadth first because it traverses the breadth of the graph as opposed to it’s close sibling DFS(depth).

Now this is here a problem. There are two types of graphs. Cyclic and Acyclic. In cyclic graphs, there are cycles, i.e loops, for example this adj list: {“A”: “B”, “B”: “A”}. If I follow BFS, you obviously see that it’ll never end the search. So no BFS in cyclic graphs. Not yet. But there is some black magic too. If we count, for each vertex, how many edges are in bound to it, called the “indegree”, then each time we visit it we can update the number of times we have been there and if we have already visited it, scrap it, don’t visit again. Nice.

Now in Acyclic graphs, BFS without any modifications can give you shortest paths to the vertices. In the above outline, the number of iterations you needed to go to a vertice is the shortest path length. Great! (obviously store the minimum, this will work for cyclic too! But a better way is just end the search when you first hit the vertex. Guess why.)

Code to solve a maze(hardcoded):

https://gist.github.com/svineet/3c961d10eb3e6943b9a8

Gives output as 4. Perfect.

Chopsticks solving using BFS next time. Stay tuned.