The World of Algorithm – Breadth First Search (BFS)

algorithms

Sharing is caring!

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 are usually defined as 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 organize 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|).

<?php

/*

* A simple iterative Breadth-First Search implementation.

* http://en.wikipedia.org/wiki/Breadth-first_search

*

* 1. Start with a node, enqueue it and mark it visited.

* 2. Do this while there are nodes on the queue:

* a. dequeue next node.

* b. if it’s what we want, return true!

* c. search neighbours, if they haven’t been visited,

* add them to the queue and mark them visited.

* 3. If we haven’t found our node, return false.

*

* @returns bool

*/

function bfs($graph, $start, $end) {

$queue = new SplQueue();

$queue->enqueue($start);

$visited = [$start];

while ($queue->count() > 0) {

$node = $queue->dequeue();

# We’ve found what we want

if ($node === $end) {

return true;

}

foreach ($graph[$node] as $neighbour) {

if (!in_array($neighbour, $visited)) {

# Mark neighbour visited

$visited[] = $neighbour;

# Enqueue node

$queue->enqueue($neighbour);

}

};

}

return false;

}

Thank you for reading this article!!!

shares