Depth First Search: Graph Searching Algorithm in Python (Rajeev Verma)

Graph Search Problem

Many problems in real-life can be easily solved by mapping them to the mathematical structure called graphs. Graph Theory and Computational Theory has led to the solution of interesting problems like Traveling Salesman problem, minimum-flow problem, etc.

In this tutorial, we will be studying and solving a very basic problem of graph searching. Consider the road network, it is practical to think if we can reach from say, Cannaught Place in Delhi to Pari Chowk in Noida and when we are at the problem of connectivity, we also want to consider the shortest path to reach it. The problem we are trying to solve is: if there is a path from place A to place B, and to say it in graph terminology; if node A and node B are connected or in general, what are the nodes which are reachable from node A.

Graph structures are ubiquitous in problems where there is an initial state and final state, and other abstract things like sequence of decisions can be considered as paths to go from initial to final state. It’s a broad and interesting topic and this tutorial will give you a flavor of it. We will code the solution to the problem of finding what are the nodes reachable from source node using Depth First Search Algorithm in Python programming language. We will be considering another algorithm called Breadth First Search in another tutorial.

We will be using Stack data-structure and you might want to review its properties and operations before proceeding further.

Depth First Search

 

 

Consider the graph above, we can see that node 5 is unreachable from all other nodes (directed edge is in opposite direction). And any other node except node 2 is unreachable from node 5. Ok so, how are we going to solve this? You won’t believe if I say that we all have solved this problem. Remember maze? Yes, starting from a source node, walk the graph as long as you are not hitting a wall. If there isn’t any forward path, start moving backwards and explore next immediate unexplored path. Simple enough?

Formally, Depth First Search (DFS) explores the graph aggressively only backtracking when necessary.

This means that starting with source node, say node 3, we will follow the nodes reachable from it recursively. A possible scenario might be, from node 3 we chose node 4, and from node 4, the only reachable node is node 2. Now, we’ve hit the wall and will backtrack. Now we are again at node 4 but there are not other nodes reachable from it (we’ve already visited node 2), so we backtrack once again and are now at node 3. It has one unexplored node 1 and we visit it. From node 1, we can reach node 2 but hey! we have already visited it. So, Backtrack.

This procedure of exploring the nodes aggressively is called depth search procedure. We are going deep into the maze and we backtrack once can’t go further. We also remember the nodes we’ve already visited and never visit them again.

This explains search procedure. Now, how are we going to implement it? Those who are aware with recursion may get a hint that all we are doing is a recursive graph traversal. For this tutorial, we are coding up a simple stack based solution as it is simple to understand. Stack is a Last-in First-Out (LIFO) based data-structure. We are using Python Collections object deque as stack implementation.

Refer the code below. Stack is maintained to backtrack. We append the node we are visiting to stack and once we can’t go further, we pop the node from the stack ( we need to pop the last visited node, that’s why stack). Parent Dictionary is maintained as a record for the nodes we have already visited.

 

Conclusion

We code up Depth First Search to graph search problem in this tutorial. Depth First Search is basic algorithm applicable to wide number of problems.

 

Add Comment

%d bloggers like this: