Insight into programming algorithms

Home » Graph Theory » Breadth-First Search(BFS) in general

Breadth-First Search(BFS) in general


Introduction

 

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors.Source.

It is more like brute forcing on a tree/graph checking all nodes at a certain depth and then moving on deeper. This isn’t generally used in path finding or problems where there are a huge amount of nodes possible since it traverses to each and every node which consumes a lot of memory. This is more used where there is no available heuristic to reach the goal and when the goal is more likely to be non-leaf nodes or closer to the root.


Prerequisite knowledge 

There are a few thing you need to know before trying your hand on programming BFS.

  • You need to know how to convert your problem into a graph i.e into nodes and edges.

This is most important stuff that you need to get right, so what is a graph? A graph is a representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices (also called nodes or points), and the links that connect some pairs of vertices are called edges (also called arcs or lines).Source.

GraphNodesEdges

Figure 1.

As shown in Figure 1 above. From programming point of view a node is where all your information is stored for a particular state of the problem, like current coordinates in pathfinding. The edge is nothing but the pointer to the next node which is stored in the previous node.The distance between each node is called the cost.

There are various types of graphs like cyclic graph, acyclic, directed cyclic,directed acyclic etc etc, explaining them will be off topic.

Let’s take the example of the water jug problem.In this particular example we have one 5 gallon jug and one 3 gallon jug, we have to collect 4 gallons.

bfs12

Figure 2.

As you see in Figure 2 the problem is converted into a tree and as you know a tree is a special case of a Directed acyclic graph(DAG) thus BFS can be applied here as well.

The figure is almost self explanatory still I’ll explain how it goes, so the nodes have data as the amount of water in each jug and these are further linked with each step possible from the previous node. As you see, the initial node is the start node where both the jugs are empty from here there are two possible states i.e either fill the 3 gallon jug or the 5 gallon jug, thus the two nodes linked to the start. Now if we see the LHS of the tree at depth 1 there are two possible steps i.e either pour the water from the 3 gallon jug to the 5 gallon jug or fill the 5 gallon jug which is described by the nodes.

This is a simple example of converting your problem space to a tree for implementation of BFS.

Note: The water in jug when poured to a container with less capacity  then the extra water will not be counted. Also the jugs can be emptied as a move.

Working

 

BFS is one of the simplest of algorithms to implement under the graph theory category of algorithms. From the implementation point of view it’s the same as that of DFS, the only difference is that here we use a queue instead of a stack. The neighboring nodes are added to the queue and this is repeated with each dequeued node from the queue.  There’s not much to it and the algorithm is self explanatory.

Here is how the nodes are traversed using BFS

animated_bfs

The grey nodes are the nodes added in the queue and the black color resembles the nodes traversed.


Algorithm

This version of algorithm is used when all the nodes are not known and the graph is created dynamically while performing the BFS, hence we use the closed_list to keep the record of traversed nodes.

root=initial node;
Goal=final node;
closed_list=empty set;                             //list of type node for unknown graph space
queue=empty queue;                                //queue of type node
function BFS()                                             //Driver function
{

queue.push(root);
while(!queue.empty())
{


current
=queue.dequeue();
if(current=Goal)                                    //Goal node found
{

return Path to goal;

}
foreach(tempnode in nextnodes(
current));  //cycle through each neighbor of current
{

if(!closed_list.exists(tempnode))
{

closed_list.insert(tempnode);
tempnode.parent=current;
queue.enqueue(tempnode);

}

}

}

}
function nextnodes(node)
{
             return list of all possible neighbouring nodes from node;
}

This version of algorithm is used when all the nodes are known and the graph known beforehand.

root=initial node;
Goal=final node;
queue= empty queue;                                //queue of type node
function BFS()                                             //Driver function
{

foreach(node in Graph)                  // mark all the nodes as not visited
              node.visited=false;
queue.push(root);
while(!queue.empty())
{

root.visited=true;
current
=queue.dequeue();
if(current=Goal)                               //Goal node found
{

return Path to goal;

}
foreach(tempnode in nextnodes(
current)); //Cycle through each neighbor of current
{

if(!tempnode.visited)
{

tempnode.visited=true;
tempnode.parent=current;
queue.enqueue(tempnode);

}

}

}

}
function nextnodes(node)
{
             return list of all possible neighbouring nodes from node;
}


If you see anything wrong with the post or if you have any queries regarding the algorithm. Post them in the comment section. There can be things wrong with this as I am still a beginner on the path of learning and this is based on what I have learnt so far with examples from external sources as well. So experts, please let me know through the comments section.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: