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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
import sys from collections import deque from collections import defaultdict #function to read the graph as adjacency list from the file def read(filename): graph = defaultdict(list) with open(filename, 'r') as f: for line in f.readlines(): graph[int(line.split('\t')[0])] = map(int, line.split('\t')[1:-1]) return graph def dfs(graph, source): stack = deque() #stack declaration parent = defaultdict(int) stack.append(source) parent[source] = 0 node = source #source node while 1: flag = True for n in graph[node]: #for the nodes reachable from node if n not in parent.keys(): #if the node is not already visited flag = False #if we are visiting a new node, mark flag as False parent[n] = node #mark it as visited stack.append(n) #append it to stack node = n #next search procedure starts from this new visited node break if flag == True: #if flag == True, we haven't visited new node, means we can't go further. stack.pop() #remove the last node for backtracking if stack: node = stack[-1] #new node to start searching from else: break return parent if __name__ == "__main__": args = sys.argv filename = args[1] source = int(args[2]) graph = read(filename) parent = dfs(graph, source) print parent |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
INPUT #python codefile graphfile source node #graph file contains tab-separated adjacency matrix 1 2 3 1 4 4 2 5 2 ! python dfs.py dfs.txt 3 OUTPUT defaultdict(<type 'int'>, {1: 3, 2: 1, 3: 0, 4: 3}) #Parent Dictionary #Note that 5 is not there. #Also, when source is 5 ! python dfs.py dfs.txt 5 OUTPUT defaultdict(<type 'int'>, {2: 5, 5: 0}) |

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