DEV Community

loading...
Cover image for Depth First Search (DFS) Algorithm

Depth First Search (DFS) Algorithm

Aya Bouchiha
Full stack web developer
・1 min read

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

Discussion (0)