The art of Depth First Search
Hello there! In today’s blog we will discuss a graph search algorithm — DFS. This blog assumes familiarity with Graphs data structure. If not, check the reference linked at the end of this blog.
What is Depth First Search?
Depth First Search essentially dictates one of the ways to explore a given graph (tree / 2d grid too)! We start with exploring a given node(vertex) and pick one of it’s neighbor and then explore that and so on until the end of that path/reach the lead node — go as farthest as you can on that path and return to the node you started with. We then pick next neighbor (vertex) and then repeat this exploration scheme.
Exploring “graphs” in general needs two types of “bookkeeping” (bookkeeping was also mentioned in my previous blog)
[a]. Track the edges or vertices that have been dealt with.
[b]. Follow a predefined order to explore new edges in the graph.
- For [a] we can use a Boolean flag to mark visited vertex/edge.
- For [b] we can either use BFS/ DFS algorithm.
Strongly connected components
This is another terminology, I want to introduce you guys to before we go deeper into DFS.
A strongly connected graph is one in which every vertex is reachable from every other vertex in the graph. In an undirected graph, this is always true. So, the concept of strongly connected components is discussed w.r.t “directed” graphs. Since, in this case, there may be cases where every vertex may not be reachable from every other vertex. For example, while representing a graph of social media followers, someone may be following you but you may not be following them back — so it’s a one-way connection. We will come back to the details of it’s usage, a little later.
Using Depth First Search
Some example scenarios where DFS comes handy are:
A. Maze problems: Find if there exists a path between two points in a maze.
[Note that this doesn’t require us to find the “shortest” path]
B. Gaming implementations: Making sure all the conditions of a given level are met before proceeding to the next level.
C. Ordering elements to respect ‘dependencies’: Designing a compiler that needs to check and order library dependencies before compilation.[Topological sort]
D. Exploring trees to do certain computations — diameter of a tree,
I do plan to cover an example problem for each of these types in later blogs. Stay tuned.
Implementing DFS algorithm
Check the pseudo-code below for the recursive and iterative implementation of DFS.
All that a basic DFS algorithm does is to explore the graph and mark vertices visited : Yes! that’s it.
Listed below are the recursive and iterative pseudo-code to do this.
// DFS routine on Graph G
// All we need to do is explore a graph G starting at vertex 'v'.DFS(G,v):
// start DFS at vertex v in graph G.
explore (G, v)// "Recursive" helper function for exploring
explore(G, v):
//This boolean flag helps in case graphs has Loops.
isVisited(n)<- True
for every edge (v,w) for given vertex v:
if not visited(w):
Explore(G,w)
For every vertex v, we explore every other vertex w that forms an edge, so the run-time of this algorithm is O(V+E), where V is the number of vertices and E is the number of edges in the graph.
In the iterative approach, we replace the recursion call with an actual stack data structure as below.
//iterative approach
DFS(G,v):
explore(G,v)// iterative explore
explore(G,v):
// set all vertices to *not visited*
// use stack data structure to maintain
// the list of vertices to be explored
Stack s = new Stack();
s.push(v); // start exploring at vertex v.
while(!(s.empty()):
x = s.pop();
if(x is not visited):
visited(x)<-True
for every edge (x,y):
if visited(y) is False:
S.push(y); // explore every unexplored neighbor vertex
end // while
end // explore
Now, the next step is to alter the above algorithm to make it a little more useful! You can explore each of the problems below to see DFS in action.
[1] Topological sort : Taking courses with prerequisites
[2] Finding islands — DFS on Matrix
[3] Find the diameter of a tree — DFS on Trees
[4] Find connected components in a graph — DFS on Graphs
Further Reading
Hope this blog was useful to you guys! In next set of blogs in this series, we will explore how above set of problems can be solved using DFS, explore BFS technique and also alternate algorithmic paradigm called “recursive backtracking” — that can be thought of as “DFS” with pruning — used to discard partial solutions as early as possible, take a step back and attempt finding a local optimum again!
Don’t forget to drop some claps below so it can reach more folks. Will see you on the next blog!~
