# Depth First Search

Depth first search can help us check if a vertex, `v`

, is connected to another vertex, `s`

, in constant time. To do so, we just check if there is a path to the vertex in the graph.

We can also find the path `v-s`

if such a path exists in time proportional to its length. To do so, we simply back-traverse the `edge_to`

array.

DFS is implemented in a recursive fashion.

## #

Pseudocode## #

Implementation## #

Time ComplexityThe time complexity for DFS is `O(|V| + |E|)`

, which is linear.

We visited each vertex once which is

`O(V)`

.DFS visit is called once per vertex where we have a cost of

`adj(v)`

=`O(Sum of adj(v) for all v)`

=`O(2E)`

=`O(E)`

Every edge is considered exactly twice, and every node is processed exactly once, so the complexity has to be a constant multiple of the number of edges as well as the number of vertices.

*Source: https://stackoverflow.com/questions/11468621/why-is-the-time-complexity-of-both-dfs-and-bfs-o-v-e**Note: For directed graphs it is just O(E) since you visit each edge once*

Total time complexity is hence

`O(|V| + |E|)`

.We can imagine this as traversing the entire data structure - each vertex has an adjacency list and we are going through the entire structure which gives us

`O(V + 2E)`

.This also means that whichever term,

`V`

or`E`

is bigger will dominate the time complexity.*Note: The time complexity is representative of the data structure used. Here, we have assumed the use of an adjacency list. If it was a adjacency matrix, it would have been*`O(V^2)`

.