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.