DEV Community

Cover image for Depth First Search (DFS) Algorithm
Aya Bouchiha
Aya Bouchiha

Posted on

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)

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

more details...

# 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')
Enter fullscreen mode Exit fullscreen mode

#day_28

References & useful Resources

Top comments (0)