##### Depth First Search

**Depth First Search**

The idea is to go 'deeper' in the graph whenever possible

**Explanation**

Again, DFS is a another very simple algorithm, Just follow the below steps of the flowchart.

We will follow the same three rules of life :

1) __Life is white sheet of paper__ : so a white vertex in graph means the vertex has not been visited yet

2) __Once you start writing your life with a pencil, it will turn gray__ : so a gray vertex in graph means the vertex is being visited

3) __Finally, you die and your ashes turn black__ __:__ so a black vertex in graph means the vertex has been visited

**Flowchart**

Let us have the below graph in the left, and an empty queue Q in the right

Now, use the flowchart and keep matching your steps with my steps:

Choose any vertex as your starting point of algorithm, let us choose vertex s. Color all vertices as white except vertex s, color vertex s as gray.

Fig 1:

Enqueue vertex s.

Fig 2:

Q is empty?

No.

dequeue(Q)

prints s

choose a neighbour of s

let us choose w

w is white?

Yes.

color w as gray

Fig 3:

Enqueue(w)

Fig 4:

choose a neighbour of s

let us choose r

r is white?

Yes.

color r as gray

Fig 5:

Enqueue(r)

Fig 6:

choose a neighbour of s

But.....see, now we don't have any white neighbour of s

so s is completed now.

color s as black

Fig 7:

Q is empty?

No.

dequeue(Q)

prints w

Fig 8:

choose a neighbour of w

let us choose t

t is white?

Yes.

color t as gray

Fig 9:

Enqueue(t)

Fig 10:

choose a neighbour of w

let us choose x

x is white?

Yes.

color x as gray

Fig 11:

Enqueue(x)

Fig 12:

choose a neighbour of w

But.....see, now we don't have any white neighbour of w

so w is completed now.

color w as black

Fig 13:

Q is empty?

No.

dequeue(Q)

prints r

Fig 14:

choose a neighbour of r

let us choose v

v is white?

Yes.

color v as gray

Fig 15:

Enqueue(v)

Fig 16:

choose a neighbour of r

But.....see, now we don't have any white neighbour of r

so r is completed now.

color r as black

Fig 17:

Q is empty?

No.

dequeue(Q)

prints t

Fig 18:

choose a neighbour of t

let us choose u

u is white?

Yes.

color u as gray

Fig 19:

choose a neighbour of t

But.....see, now we don't have any white neighbour of t

so t is completed now.

color t as black

Fig 20:

Q is empty?

No.

dequeue(Q)

prints x

Fig 21:

choose a neighbour of x

let us choose y

y is white?

Yes.

color y as gray

Fig 21:

**Psuedocode**

1. DFS(G)

2. {

3. for each vertex s in G:

4. {

5. s.color=white;

6. }

7. for(all vertices s in G)

8. {

9. if(s.color==white)

10. {

11. DFS_VISIT(G,s);

12. }

13. }

14. }

15. DFS_VISIT(G,s)

16. {

17. s.color=gray;

18. print(s);

19. for(all neighbours v of s)

20. {

21. if(v.color==white)

22. {

23. DFS_VISIT(G,v);

24. }

25. }

26. s.color=black;

27. }

__Time complexity__

DFS has a time complexity of O(V+E) if we have graph stored in an adjacency list, and O(V^{2}) if we have graph stored in an adjacency matrix.