Breadth First Search in PHP Tutorial

Udemy Generic 728x90

Objective

In this tutorial we will learn the concept of Breadth First Search algorithm and process to implement them in PHP code.

 

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.

Step 2

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:

  1. Enqueue, i.e. push the source node as the root node in queue.
  2. Dequeue, i.e. remove  the node from the queue and examine its successors :
    • If successors are found, then enqueue them.
    • Else return:
  3. If the Queue is empty, quit the search as every node of the graph has been traversed.
  4. It the Queue is not empty, then repeat step 2.

A simple example to illustrate how Breadth First Search works :

Step 2.1

Array Representation of Graph

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

Step 2.2

Graphical Representation

BFS

Step 3

Complexity analysis

 

Step 3.1

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|). 

 

Step 3.2

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|).

 

Step 4

PHP implementation of BFS Algorithm

<br />
&lt;?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 =&gt; $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 =&gt; $vertex) {</p>
<p>            if (!$visited[$key] &amp;&amp; $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 />
?&gt;<br />

Step 4.1

Output

Array ( [2] => 1 [0] => 1 [3] => 1 [4] => 1 [5] => 1 [1] => 1 )
Udemy Generic 728x90

Spread the word. Share this post!

  • JackFrost

    This is what i am looking for though i am not trying it yet. Good post!