Objective

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

## 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:

- Select a source node.
- Check the untraversed edges out of that node.
- If found then traverse through one of the untraversed edge to its child vertex.
- 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**.

- If yes, then repeat from Step
- If not then check if any undiscovered vertices remains.
- If yes, then repeat from Step
**1**. - Else terminate the execution.

- If yes, then repeat from Step

A simple example to illustrate how **DFS** 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(|*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*|).

## PHP implementation of DFS Algorithm

<br /> <?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->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->len = count($this->graph);<br /> $this->init();<br /> }</p> <p> function init(){</p> <p> for ($i = 0; $i < $this->len; $i++) {<br /> $this->visited[$i] = 0;<br /> }<br /> }</p> <p> function depthFirst($vertex){</p> <p> $this->visited[$vertex] = 1;</p> <p> for ($i = 0; $i < $this->len; $i++) {</p> <p> if ($this->graph[$vertex][$i] == 1 && !$this->visited[$i]) {<br /> $this->depthFirst($i);<br /> }<br /> }<br /> echo "$vertex <br>";<br /> }<br /> }</p> <p>$g = new Graph();<br /> $g->depthFirst(2);</p> <p>?><br />

### Output

5 4 3 1 0 2