Graph Algorithms : Depth First Search

Graphs are used everywhere. In social networks, drug discovery, search engines, maps etc. As a software engineer, it’s imperative that you are well-versed with the concepts of graph theory and be able to solve graph problems. Today let’s go over a fundamental graph searching algorithm known as depth first search. For those unfamiliar with graph theory, there is a fantastic blog post on it here.

Coding Up A Graph

One of the biggest problems I face when trying to code graph based solutions, is to visualize the problem in a simple way. Which is why I think it is necessary to be able to represent the graph data structure such that it could be modified and used as a template for all problems. Let’s implement the graph data structure using a simple Python class.

Simple Graph

There are two main representations of the relationships in a graph.

• Adjacency List : It is a list of nodes and their neighbors. Looks something like this

0 : [1]
1 : [0, 2, 3]
2 : [1, 3]
3 : [2, 1]

• Adjacency Matrix : It is a matrix, represented by 0’s and 1’s or an integer depending on the type of graph (weighted, directed etc.). Looks something like this

   0 1 2 3
0  0 1 0 0
1  1 0 1 1
2  0 0 0 3
3  0 1 1 0

In this implementation I will be using the adjacency list representation. The matrix method is also very useful and we can discuss it when solving coding problems in upcoming blog posts.

Depth First Search

The depth first search algorithm is a graph traversal algorithm where the nodes/vertices in a graph are traversed in the order of depth. Check out the example below

DFS Example

This is a very powerful algorithm and is used frequently when solving graph based puzzles/coding problems. The depth first search algorithm has the following steps :

1. Maintain a list of visited nodes/vertices in the graph
2. Pick a starting vertex. If the vertex has not been visited then, add it to the visited list and repeat the same on all it’s adjacent nodes.
3. Repeat until all vertices have been visited.

Below is the implementation of this algorithm. This approach follows a recursive method.

DFS using recursion

The traditional DFS algorithm, uses a stack to traverse the graph (it is a slight modification of the recursive edition). The steps for this algorithm are given below :

1. Maintain a list of visited nodes/vertices in the graph.
2. Pick a starting vertex. If the vertex has not been visited, add it to the visited list. Now, push it into a stack.
3. If no adjacent, vertex is found, pop current vertex from the stack.
4. Repeat steps 2 and 3 until the stack is empty.

The implementation is given below.

DFS using stack

The complexity of the DFS algorithm over an adjacency list is O(V+E). Where V denotes the vertices and E the edges. In the next blog post, we will be going over another graph search algorithm knows as the breadth first search. Stay tuned !

References

1. https://jovian.ai/aakashns/python-graph-algorithms
2. https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/
3. https://www.educative.io/edpresso/how-to-implement-depth-first-search-in-python
4. https://www.tutorialspoint.com/data_structures_algorithms/depth_first_traversal.htm