Depth first search (DFS) is an algorithm for searching graph or tree type data structures. Another algorithm Breadth first search (BFS) is often heard with DFS. The purpose of these algorithims are same - traversing a graph or three. However, there are some fundamental difference in implementation. DFS uses a stack and BFS uses a queue for their data structure. In this article I'll traverse a graph using DFS algorithm.
Lets consider this graph. This is a directed graph as the vertices are connected by directed edges. Graphs are normally represented using Adjacency List and Adjacency Matrix in programming. We can use adjacency list for this. In python an adjacency list can be represented as a dictionary data structure. Thus the adjacency list of this particular graph will look like bellow.
graph = {
'a': ['b', 'c'],
'b': ['c', 'e'],
'c': ['d'],
'd': ['e'],
'e': []
}
I'll use two approach to traverse this graph. Recursive and non-recursive. Lets try the non-recursive approach first. For this we will maintain a stack for pushing the vertices to be visited. And once a vertex is visited we will store it in a separate list or set. This list or set will contain the vertex we have visited already.
def dfs(graph, root):
stack = [root]
visited = set()
while len(stack) > 0:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
print(vertex)
for adj_vertex in reversed(graph.get(vertex)):
stack.append(adj_vertex)
We will pass the graph itself and a starting point. If we call this fuction the output would be like this:
a b c d e
Another approach is the recursive approach.
def dfs_recursive(graph, root, visited=None):
if visited is None:
visited = set()
if root not in visited:
visited.add(root)
print(root)
for node in graph.get(root):
dfs_recursive(graph, node, visited)
For recursive approach we don't need to maintain the stack explicitly. Recursion uses a call stack uses for it's method calls. The output of this is also similar to the non-recursive approach.