DEV Community

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

Posted on

4 1

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

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

AWS GenAI LIVE!

GenAI LIVE! is a dynamic live-streamed show exploring how AWS and our partners are helping organizations unlock real value with generative AI.

Tune in to the full event

DEV is partnering to bring live events to the community. Join us or dismiss this billboard if you're not interested. ❤️