Depth First Search (DFS) Algorithm

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)

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

more details...

# code from https://www.educative.io/edpresso/how-to-implement-depth-first-search-in-pythongraph = {    '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

References & useful Resources

• https://www.educative.io/edpresso/how-to-implement-depth-first-search-in-python

• https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/

• https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/tutorial/