## Exploring the Basics of Depth First Search (DFS) Algorithm

Tuesday, 18 Oct 2022 3 minutes read

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:
print(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:
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.