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