Algorithms and The Different Types of Algorithms - Breadth First Search - BFS

feature-top

The programmers who are responsible for all the technology we are enjoying today had to know about the art of using algorithms, in their code. As a software engineer knowing and learning about the different types of algorithms that exist today, to use in any programming language, should be basic knowledge.

Graphs are a particular data set, which is usually defined as a pair of sets (A, B), where A is the set of arbitrary objects known as vertices or nodes, and B is the pair of vertices known as edges or arcs.

In today's article, we are going to talk about the Breadth First Search (BFS) algorithm, to understand how a graph may be traversed.

Every vertex and edge of a graph is searched in a well-defined order only one time, in graph traversing algorithms. Every vertex of a graph must only receive one visit and the order in which the vertex is visited depends on the algorithm used to solve a problem.

When a vertex of the graph has been visited, it is important to keep track of that vertex, by marking that vertex, which is the most common way of tracking vertices. In BFS traversing algorithm, a node is selected from the graph, to start the traversing process, which takes place layer by layer.

The nodes that are directly connected to the source or selected node, are explored then the next layer of neighbor nodes is explored. So that is the algorithm, is two steps, first move horizontally and visit all the nodes of the current layer, starting from the source node; then move to the next layer of nodes and move horizontally through that layer.

But what if a graph contains a cycle? You may end processing the same node again, which is a big red flag for traversing graphs. So as explained before, the node would have to be marked and in order to accomplish this, a Boolean array can be used.

The BFS algorithm traverses a graph in a breadth-ward motion, and to remember to get to the next vertex of the graph, a queue is used to begin, the search. The BFS algorithm visits nodes in the layer of a graph and stores them so that it is traversing the corresponding, child nodes.

The First In First Out or FIFO queuing method is followed by the queue, which means that the node that is inserted first is visited first as well until all the nodes are visited. Traversing a graph is the most fundamental graph problem, therefore, the most fundamental algorithms on graphs, are applying graph traversal.

We should keep in mind that the data is used by the algorithm of interest, to accomplish a task. Therefore, the way that data is organized is very important when it comes, to the design and analysis of algorithms.

The time complexity of the BFS would be, for a graph G = (A, B), O(|A| + |B|), because the operation to push and pop a vertex from queue in BFS takes O(1) time, and for all vertices it would be O(A). The scanning of each vertex that is adjacent to the source happens at least once, when the vertex is popped from the queue, therefore the time spent to scan the adjacent nodes is O(B), therefore the time complexity of BFS is O(|A| + |B|).  

Thank you for reading this article!!!

feature-top
feature-top
Hernando Cadet

Hi every one, I obtained a bachelor's degree in Bioinformatics back in 2006, from Claflin University, after I received my bachelor's degree, I gained full time employment as a software engineer at a Video Relay Service company, maintaining databases and developing software for a new developed device called the VPAD.

I worked at that company for two years, then I became a web developer, and worked for a magazine for three years. After that job, I worked as a Drupal web developer, as a subcontractor for the NIH, for a year and then left the job to go back to school.

Hernando Cadet Hi every one, I obtained a bachelor's degree in Bioinformatics back in 2006, from Claflin University, after I received my bachelor's degree, I gained full time employment as a software engineer at a Video Relay Service company, maintaining databases and developing software for a new developed device called the VPAD.

I worked at that company for two years, then I became a web developer, and worked for a magazine for three years. After that job, I worked as a Drupal web developer, as a subcontractor for the NIH, for a year and then left the job to go back to school.