Depth First Search in PHP Tutorial

Udemy Generic 728x90

Objective

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

 

Depth First Search is a searching algorithm to search or traverse a given graph or tree data structure. The strategy followed by DFS is to search deeper in a graph until the end is met.

DFS progresses with root node and explores an edge to one of its child vertex and then explores the edges out of the most recently discovered vertex leaving other undiscovered edges. Once all the edges of child vertex has been explored then backtracks to the root node to explore the undiscovered edges from the root node. This process continues till all the vertices reachable from the source vertex are explored. After the all reachable vertices been explored, if any vertices remain then DFS selects one of them as new sources and repeats the whole process.

 

Step 2

Algorithm

The algorithm starts from the source node, selects one of its edges and traverse via vertices in its path towards the depth of the graph leaving other edges in the same level untraversed.

This algo has following 5 steps:

  1. Select a source node.
  2. Check the untraversed edges out of that node.
  3. If found then traverse through one of the untraversed edge to its child vertex.
  4. Check if child vertex have any untraversed edges out of it.
    • If yes, then repeat from Step 3.
    • Else return the element and backtrack to its parent node and repeat from Step 2.
  5. If not then check if any undiscovered vertices remains.
    • If yes, then repeat from Step 1.
    • Else terminate the execution.

A simple example to illustrate how DFS 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

DFS
DFS

Step 3

Complexity analysis

Time Complexity : O(|E| + |V|)

Suppose we have a graph G = (V, E) where E represents the edges and V represents vertices of the graph.
DFS traverses through the entire graph hence time taken will be O (E). The overhead of initialization will be O (V). So total time taken by DFS will be O (V +E).
Now as we know that a graph can be represented two standard ways : Adjacency List and Adjacency Matrix.
So in case of adjacency list , if the graph is sparse then value of |E| tends to number of vertices in the graph. Hence, best case performance will be O (V).
If the graph is dense then value of |E| -> V^2. So the worst case performance of DFS is O (V^2).

Space Complexity : O(|V|).

In DFS we need to stack all the vertices in the current path and all the already visited vertices. So the max size for stack is V. So the space complexity of DSF for a graph G = (V, E) will be O(|V|).

 

Step 4

PHP implementation of DFS Algorithm

<br />
&lt;?php</p>
<p>class Graph{</p>
<p>    private $len = 0;<br />
    private $graph = array();<br />
    private $visited = array();</p>
<p>    public function __construct(){</p>
<p>        $this-&gt;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>        $this-&gt;len = count($this-&gt;graph);<br />
        $this-&gt;init();<br />
    }</p>
<p>    function init(){</p>
<p>        for ($i = 0; $i &lt; $this-&gt;len; $i++) {<br />
            $this-&gt;visited[$i] = 0;<br />
        }<br />
    }</p>
<p>    function depthFirst($vertex){</p>
<p>        $this-&gt;visited[$vertex] = 1;</p>
<p>        for ($i = 0; $i &lt; $this-&gt;len; $i++) {</p>
<p>            if ($this-&gt;graph[$vertex][$i] == 1 &amp;&amp; !$this-&gt;visited[$i]) {<br />
                $this-&gt;depthFirst($i);<br />
            }<br />
        }<br />
        echo &quot;$vertex &lt;br&gt;&quot;;<br />
    }<br />
}</p>
<p>$g = new Graph();<br />
$g-&gt;depthFirst(2);</p>
<p>?&gt;<br />

Step 4.1

Output

5 4 3 1 0 2
Udemy Generic 728x90

Spread the word. Share this post!

  • Boggy

    can u share adjancy matrix .Deapth First Search More.i need for my project with php.

  • Tasta Jaya Gulo

    Please help, how to implement into php mysqli? thank you