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

void search(Node root) {
if(root == null) {
return;
}
visit(root);
root.visited = true;
for each (Node n in root.adjacent) {
if(n.visited == false) {
search(n);
}
}

## Implementation#

class DepthFirstPaths:
def __init__(self, g, s):
self.marked = {} # keeps track of which vertices have been visited
self.init_marked(g.get_vertices())
self.edge_to = {} # maintains edges to vertices
self.s = s # source
self.dfs(g, s)
def init_marked(self, vertices):
for vertex in vertices:
self.marked[vertex] = False
def dfs(self, g, s):
self.marked[s] = True
# for every node adjacent to current node, we pick them and dfs again
for w in g.get_vertex(s).get_connections():
id = w.get_id()
if(id in self.marked and not self.marked[id]):
self.dfs(g, id)
self.edge_to[id] = s
def has_path_to(self, v):
if(v in self.marked):
return self.marked[v]
else:
return False
def path_to(self, v):
if(not self.has_path_to(v)):
return None
else:
path = [v]
x = v
while(x != self.s):
path.append(self.edge_to[x])
x = self.edge_to[x]
return path
def get_marked(self):
return self.marked
def get_edge_to(self):
return self.edge_to

## Time Complexity#

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

• v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges) =
(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]

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