Objective

Searching, in terms of graph means systematically following the edges of graph to visit the vertices. **Breadth First Search **is one of the simplest algorithms for searching a graph.

Assume that we have a graph G and source vertex **s. **So Breadth first search algo systematically explores all the edges to discover vertex that is reachable from the source. This algorithm first searches all the vertices at level **N** from root node before going to the next level, that’s why it is named as **BFS** algorithm. Basically, it computes the smallest distance from the source to each reachable vertex. After discovering all the reachable vertex, it also produces a **breadth first tree** with the source as its root node. This algorithm works both for directed and undirected graph.

## Algorithm

The algorithm starts from the source and traverse through the graph until the last level. It uses a **Queue** data structure to store the intermediate result as it traverse through the graph.

This algo has following four steps:

- Enqueue, i.e. push the source node as the root node in queue.
- Dequeue, i.e. remove the node from the queue and examine its successors :
- If successors are found, then enqueue them.
- Else return:

- If the Queue is empty, quit the search as every node of the graph has been traversed.
- It the Queue is not empty, then repeat step 2.

A simple example to illustrate how Breadth First Search works :

### Array Representation of Graph

<br /> array(<br /> 0 => array( 0, 1, 1, 0, 0, 0 ),<br /> 1 => array( 1, 0, 0, 1, 0, 0 ),<br /> 2 => array( 1, 0, 0, 1, 1, 1 ),<br /> 3 => array( 0, 1, 1, 0, 1, 0 ),<br /> 4 => array( 0, 0, 1, 1, 0, 1 ),<br /> 5 => array( 0, 0, 1, 0, 1, 0 )<br /> );<br />

### Graphical Representation

## Complexity analysis

### Time Complexity

O(|*V*| + |*E*|),

where *V* is no. of vertices and *E* is no. of total edges in adjacency list of graph G = (*V, E*).

As we know that each vertex in **BFS** are pushed and popped from queue at most once. Each of the operation takes O(1) time, so total time taken for all the vertices will be O(*V*).

Now the adjacency list of each vertex is scanned by procedure only when that vertex is popped from the queue. So the adjacency list of each vertex will be scanned by the procedure at most once. So time spent in scanning of all the adjacency lists will be O(*E*).

The overhead of initialization will be O(*V*), so the total running time of **BFS** is O(|*V*| + |*E*|).

### Space Complexity

O(|*V*|).

In **BSF** we use queue to keep track of each visited vertex and every vertex is visited at most once. So the max size of queue is *V*. So the space complexity of **BSF** for a graph G = (*V, E*) will be O (|*V*|).

## PHP implementation of BFS Algorithm

<br /> <?php</p> <p>$graph = array(<br /> array(0, 1, 1, 0, 0, 0),<br /> array(1, 0, 0, 1, 0, 0),<br /> array(1, 0, 0, 1, 1, 1),<br /> array(0, 1, 1, 0, 1, 0),<br /> array(0, 0, 1, 1, 0, 1),<br /> array(0, 0, 1, 0, 1, 0),<br /> );</p> <p>function init($visited, $graph){</p> <p> foreach ($graph as $key => $vertex) {<br /> $visited[$key] = 0;<br /> }<br /> }</p> <p>function breadthFirst($graph, $start, $visited){</p> <p> $visited = array();<br /> $queue = array();</p> <p> init($visited, $graph);<br /> array_push($queue, $start);<br /> $visited[$start] = 1;</p> <p> while (count($queue)) {</p> <p> $t = array_shift($queue);</p> <p> foreach ($graph[$t] as $key => $vertex) {</p> <p> if (!$visited[$key] && $vertex == 1) {<br /> $visited[$key] = 1;<br /> array_push($queue, $key);<br /> }<br /> }<br /> }<br /> print_r($visited);<br /> }</p> <p>breadthFirst($graph, 2);<br /> ?><br />

### Output

Array ( [2] => 1 [0] => 1 [3] => 1 [4] => 1 [5] => 1 [1] => 1 )