Depth Search (DFS) Algorithm in Python

Introduction

In depth-first search (DFS), all nodes are scanned along some branch and backtracked. Think of it like being in a maze: DFS follows one path until it reaches a dead end before retracing its steps to take another, right? It is the same as downloading, validating the tunnel, etc. for all tunnels.

DFS is useful for:

• Visit each node in a graph.
• Checking how the different nodes are connected.

While DFS drills down, another method called Breadth-First Search (BFS) checks all neighbors at the current level before drilling down. Both methods are important, but depth-first search (DFS) helps you get as far down one path as possible before trying another.

The summary

• DFS will exhaustively visit a single path before backtracking to a node with an unvisited path.
• DFS-Recursive uses a call stack to manage the traversal and drills down into each path.
• It uses a separate stack to maintain scanning; therefore, there is no recursion depth problem.
• The time complexity of DFS is O(V+E)O(V+E)O(V+E), and its space complexity is O(V)O(V)O(V).
• DFS is great for many things. Some of the most common are path finding, cycle detection, topological classification, and puzzle solving.
• Difference between DFS and BFS BFS explores each level first and then moves to the next, while DFS goes through a branch and then moves to the current one.

How does depth-first search (DFS) work?

The DFS algorithm involves visiting nodes as deeply as possible before backtracking. Here is a step-by-step explanation:

1. Starting node: The search will start at the root node, in the case of a tree, or from an arbitrary node, in the case of the graph.
2. Visit: Mark the node as visited.
3. Explore: For each adjacent node, recursively visit the node if you have not already visited it.
4. Retract: When a node is reached with no unvisited adjacent nodes, roll back to the previous node and continue the process.

Also Read: A Complete Python Tutorial to Learn Data Science from Scratch

Depth Search (DFS) Algorithm

DFS: Depth-first search is a recursive algorithm. To implement it for a graph, we can use recursion or implicit recursion using Stack.

Recursive implementation

The recursive implementation of DFS leverages the call stack to manage state traversal. Here is a Python implementation:

Code:

def dfs_recursive(graph, node, visited):

    if node not in visited:

        print(node, end=' ')

        visited.add(node)

        for neighbour in graph(node):

            dfs_recursive(graph, neighbour, visited)

# Example usage:

graph = {

    'A': ('B', 'C', 'D'),

    'B': ('E'),

    'C': ('G', 'F'),

    'D': ('H'),

    'E': ('I'),

    'F': ('J'),

    'G': ('K')

}

visited = set()

print("DFS traversal using recursive approach:")

dfs_recursive(graph, 'A', visited)

Iterative implementation

The iterative implementation uses an explicit stack to manage traversal. This can be useful to avoid potential problems with depth of recursion in languages ​​that limit call stack size.

Code:

def dfs_iterative(graph, start):

    visited = set()

    stack = (start)

    while stack:

        node = stack.pop()

        if node not in visited:

            print(node, end=' ')

            visited.add(node)

            stack.extend(reversed(graph(node)))  # Add in reverse order to maintain the order of traversal

# Example usage:

graph = {

    'A': ('B', 'C', 'D'),

    'B': ('E'),

    'C': ('G', 'F'),

    'D': ('H'),

    'E': ('I'),

    'F': ('J'),

    'G': ('K')

}

print("\nDFS traversal using iterative approach:")

dfs_iterative(graph, 'A')

Explanation

The code examples refer to the graph as an adjacency list. Each node is like a key and lists all the nodes directly connected to it. To avoid revisiting the same node, we have a set called visited, which stores the previous node.

• Recursive DFS: The dfs_recursive function calls itself for each unvisited neighbor of the current node, drilling down each path.
• Iterative DFS: The dfs_iterative function uses a stack (a list where you add and remove elements) to manage which nodes to visit next. This stack works like the call stack in the recursive method, which helps keep track of the order of visits.

Both methods ensure that all parts of the graph are explored, but they do so in different ways.

Complexity of time and space

Here is the time and space complexity of DFS:

• Time complexity: The time complexity of DFS is O(V + E), where V and E are the number of vertices and edges, respectively. In the worst case, each vertex and edge will be searched once.
• Space complexity: The space complexity would be O(V) since we need to keep track of the nodes visited. In recursion, we would run a recursion stack or we can insert nodes into the stack iteratively.

Applications of Depth Search (DFS)

Depth First Search (DFS) It has numerous applications in computing and real-world problems:

• Pathfinding: DFS would be useful for finding a path between two nodes in a graph.
• Cycle detection: It helps detect cycles in a graph and is useful in various domains such as dependency resolution.
• Use cases for topological classification: Schedule tasks so that each task depends on the others and must be performed in linear order.
• Graphics and Connected Components Tour: DFS on an undirected graph to identify all connected components.
• Maze and puzzle solving: Solve complex mazes and puzzles by following all possible paths.

Real world example

Suppose you have to find all the routes in a computer network so that data is transmitted correctly. DFS is an algorithm that performs depth-first search on a graph. It can be used to start from a particular computer and follow connections as far as they go, backtracking when no more connections can be followed.

Code:

def find_paths(graph, start, end, path=()):

    path = path + (start)

    if start == end:

        return (path)

    if start not in graph:

        return ()

    paths = ()

    for node in graph(start):

        if node not in path:

            new_paths = find_paths(graph, node, end, path)

            for p in new_paths:

                paths.append(p)

    return paths

# Example usage:

network = {

    'Computer1': ('Computer2', 'Computer3'),

    'Computer2': ('Computer4'),

    'Computer3': ('Computer4', 'Computer5'),

    'Computer4': ('Computer6'),

    'Computer5': ('Computer6'),

    'Computer6': ()

}

start="Computer1"

end = 'Computer6'

print(f"All paths from {start} to {end}:")

paths = find_paths(network, start, end)

for path in paths:

    print(" -> ".join(path))

DFS vs. BFS

While DFS drills down into a graph, BFS explores all of a node's neighbors before moving to the next level. Each one has its advantages:

• DFS: It uses less memory and can find a route without exploring all nodes.
• BFS: Guarantees to find the shortest path in an unweighted graph.

Conclusion

DFS, or depth-first search, is a powerful utility for traversing graphs and using them in tree problems. DFS is useful for solving puzzles, finding your way in a maze, or organizing tasks. The two ways to use DFS are:

• Recursive DFS– This uses function calls to track where it is coming from in the graph.
• Iterative DFS: Use a battery to handle the steps.

The 2 methods guaranteed full graph coverage; each node was explored. Here is a list of how DFS can find paths, detect cycles, order tasks, and connect components in a graph. Gaining knowledge about DFS will help you solve difficult problems. After seeing the examples, you can explore DFS in your code.

So, are you looking for online Python courses? If yes, explore – Introduction to Python today!

Frequent questions