Hi, today, we're going to talk about Depth First Search (**DFS**)

## Definition of Depth First Search

- Depth First Search: is an algorithm for traversing or searching in tree or graph data structure using recursion and
**Stack**data structure.

## Time & Space complexity of Depth First Search (DFS)

Space complexlity | O(V) |
---|---|

Time complexity |
O(V+E) |

## Depth First Search applications

- Counting connected components
- Solving Sudoku Puzzles
- Topological sorting
- Pathfinding
- Finding Strongly Connected Components of a graph

## Depth First Search implementation in Python

```
# code from https://www.educative.io/edpresso/how-to-implement-depth-first-search-in-python
graph = {
'A' : ['B','C'],
'B' : ['D', 'E'],
'C' : ['F'],
'D' : [],
'E' : ['F'],
'F' : []
}
visited = set() # Set to keep track of visited nodes.
def dfs(visited, graph, node):
if node not in visited:
print(node)
visited.add(node)
for neighbour in graph[node]:
dfs(visited, graph, neighbour)
dfs(visited, graph, 'A')
```

#day_28

## Top comments (0)