Searching wide: breadth-first search, part I

The second post in our AI coding tutorial series.

The art of coding. Credit: Benoit Vallon

Welcome back, AI coders in the making. Last time, we introduced search. We learnt that before jumping to any solutions, we first have to understand the problem, and model the space with a well-defined representation. In the next few posts, we’ll look at the theory and implementation of a specific AI search algorithm called breadth-first search (BFS).

Before we get started, we’d like to send some good old human gratitude to a brilliant community hero for porting all our code to Go. Massive thanks, Vasanth Kumar, @Vasanth_trot.

Types of search

There are two main types of search algorithms: informed search and uninformed search. An uninformed search algorithm doesn’t use any domain knowledge to solve a problem. In other words, it has no information to help it arrive at a solution. BFS is one such algorithm. Informed search, on the other hand, uses heuristics (imperfect practical methods, like a rule of thumb) that estimate the closeness to the goal. If you’re a games developer, you might have heard of A*, a fundamental informed search algorithm.

Imagine we’re searching for a source of radioactivity. Using our trusty Geiger counter, we could listen to the clicks to get an idea of whether we’re moving closer to the radioactive source, or further away. This is informed search, because we’re using some domain knowledge to aid us. Without the Geiger counter it would be like stumbling blindly through a nuclear wasteland, not knowing where to go — that’s uninformed search. Uninformed search is the unexciting way to search, because we don’t leverage any domain knowledge about a problem. But, despite its dullness, (spoiler alert) it pays off.

BFS can be used to traverse graph data structures. In other words, BFS implements a specific strategy for visiting all the nodes (or vertices) of a graph via their edges. If this data structure sounds familiar, it’s because we’ve already looked at a similar data structure in the last post; except there we called it a tree. You might be wondering what the difference is between a graph and a tree. Let’s have a look.

The Graph Data Structure

A graph with seven nodes (the circles) and seven edges (the lines).

The figure above shows a connected graph with seven nodes and seven edges. The edges are undirected and unweighted. The distance between two nodes can be measured by counting the number of edges separating them. For example, the distance from A to B is one, but the distance from A to G is two.

Code-wise, you can represent a graph in a couple of ways: an adjacency matrix (a two-dimensional list useful for dense graphs) or an adjacency list (useful for sparse graphs). Here we’ll use the adjacency list and, wouldn’t you know it, in the last post we also used an adjacency list.

Last time I assigned integer IDs to all the nodes (states) in the graph and used a list to link them. In this example we have string IDs (A to G), so we’ll use dictionaries instead of lists. The keys of the dictionary will represent the nodes, while the values will have a list of the connected neighbours.

Here’s how we can represent the above graph as a python dictionary:

In the code above, the first item of the dictionary (line 2) tells us that the “A” node’ is connected with the “B”, “C” and “E” nodes, also clearly shown in the above graph.

If you take a moment to compare the above code with the example tree code from last week, there’s not much difference between the two. Here we’re using dictionaries, strings and lists instead of lists and integers. That’s basically it. So why did we call last post’s structure a tree, and this one a graph? Well, it’s because I lied — sorry!

In actual fact, a tree is a special kind of graph, where certain conditions are met. Let’s take the base definition of a graph, where nodes connect with edges. If the edges are unidirectional and there is only one edge between each node, following a parent-child relationship, then that graph can be called a tree. There are a few more rules, but that’s the gist of it. The real reason why we referred to the graph in last week’s post as a tree, was that trees are easier to visualise and understand for beginners. I hope you can forgive me; I’d only ever lie to you for your for your own education. Besides, in our example graph above, the right side of the graph is a tree.

For now, we’ll focus on the more general structure of the graph.

Understanding BFS with graphs

As you’ve hopefully seen by now, search algorithms are inherently tied to the concept of a graphs. That’s because a graph is an elegant way of representing a search space.

BFS searches the graph in a very simple and effective way. First, it starts with an initial node, then checks the neighbours of that node, then the neighbours of the neighbours, and so on, until all the nodes have been ‘visited’, or explored. Hopefully, with enough perseverance and cups of coffee, we’ll eventually find our goal state.

BFS visits all the nodes of a graph following a breadthward motion (hence the name). In other words, BFS starts from a node, then checks all the nodes at distance one from the starting node; then it checks all the nodes at distance two, and so on.

To remember which nodes to visit, BFS uses a queue. The algorithm can keep track of the nodes it’s already checked to avoid revisiting them, in case a graph had one or more cycles.

The BFS Algorithm

The BFS algorithm follows the following steps:

1. Add the starting node to the queue.
2. Remove the next node from the queue.
3. Check if the node has already been explored.
4. If not, add all the neighbour nodes to the queue.
5. Mark the node as explored.
6. Loop through steps 2 to 5 until the queue is empty.

To implement the BFS queue, a FIFO (First In, First Out) queue is used. In FIFO queues, the oldest (first) entry is processed first. The process is similar to what happens in queues at the post office — first come, first served.

Following this algorithm, the nodes in our example graph would be visited in this order:

The order in which BFS visits the nodes of the graph.

Looking at the figure above, it’s clear why BFS follows a breadthward motion. The algorithm checks all the nodes at a given depth (distance from the entry point), before moving to the level below. This means BFS works in horizontal slices.

Implementing BFS

Visiting all the nodes of a graph with BFS is as simple as implementing the steps of the above algorithm.

Let’s first initialise a couple of lists that we’ll use to keep track of nodes visited, and those yet to be checked.

As you can see, the FIFO queue already has a node to be checked, i.e., the starting node that is used as an entry point to explore the graph. The next step is to implement a loop that keeps cycling until the queue is empty. At each iteration of the loop, a node is checked. If this node wasn’t visited already, its neighbours are added to queue.

Once the while loop is exited, the function returns all of the visited nodes. Mission accomplished! We now have a functioning BFS implementation that traverses a graph.

Here’s a couple of tasks you can do to test what you’ve learned:

1. Implement the FIFO queue using the deque object from the python collections module instead of a list. This way you can use the popleft() method instead of the pop(0) built-in function on the list. What is the benefit of doing this?
2. Can you change the BFS implementation in order to return the shortest path between the nodes “G” and “D” of the example graph we’ve been using?

Don’t worry if you can’t do these challenges! You can find the code to the above, as well as my solutions to the tasks in our Git repo. Next time I’ll thoroughly explore the solution to task two; you won’t have to search too wide to find it.

Continue your training to supreme master-level AI coding here.

And give us a follow to receive updates on our latest posts.