Implementation of Depth First Search (DFS) Algorithm in Python

Introduction

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

DFS is useful for:

• Visiting every node in a graph.
• Checking how different nodes are connected.

While DFS dives deep, another method called Breadth-First Search (BFS) checks all neighbors at the current level before moving deeper. Both methods are important, but Depth First Search (DFS) helps you go as far as possible down one path before trying another.

The Overview

• DFS will exhaustively visit a single path before backtracking to a node with an unvisited path.
• DFS-Recursive uses a call stack to manage traversal and goes deeper into each path.
• Uses a separate stack to maintain the exploration; therefore, no recursion depth problem.
• DFS’s time complexity is O(V+E)O(V + E)O(V+E), and its space complexity is O(V)O(V)O(V).
• DFS is cool for many things. Some of the most common are pathfinding, cycle detection, topological sorting, and puzzle solving.
• Difference between DFS and BFS BFS explores each level first and then goes to the next level, whereas DFS goes through one branch and then moves to the current.

How Does Depth First Search (DFS) Work?

The DFS algorithm involves visiting nodes as deeply as possible before backtracking. Here’s 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 node as visited.
3. Explore: For each adjacent node, recursively visit the node if it has not been visited yet.
4. Backtrack: When a node with no unvisited adjacent nodes is reached, backtrack to the previous node and continue the process.

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

Depth First Search (DFS) Algorithm

DFS—Depth First Search is a recursive algorithm. To implement it for a graph, we can either use recursion or implicit recursion using Stack.

Recursive Implementation

The recursive implementation of DFS leverages the call stack to manage the traversal state. 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 the traversal. This can be useful to avoid potential issues with recursion depth in languages that limit the 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, listing all the nodes directly connected to it. To avoid revisiting the same node, we have a set named visited, which stores the previous node.

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

Both methods ensure all parts of the graph are explored, but they do it differently.

Time and Space Complexity

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: Space complexity would be O(V) since we need to keep track of visited nodes. In recursion, we would run a recursion stack, or we may push nodes into the stack in iterative.

Applications of Depth First Search (DFS)

Depth First Search (DFS) has numerous applications in computer science 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, like dependency resolution.
• Use cases for topological sorting: Scheduling the tasks so that each task depends on the others and must be performed in linear order.
• Graph Traversal & Connected Components: DFS in an undirected graph to identify all connected components.
• Maze and Puzzle Solving: Solve complex maze and puzzles by traversing every possible path.

Real-World Example

Suppose you have to find all the paths in a network of computers so that the data will be transmitted correctly. DFS is an algorithm that performs a depth-first search in 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 dives deep into a graph, BFS explores all neighbors of a node before moving to the next level. Each has its advantages:

• DFS: Uses less memory and can find a path without exploring all nodes.
• BFS: Guarantees finding 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 when 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 you are coming from in the graph.
• Iterative DFS: Using a stack to handle the steps.

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

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

Frequently Asked Questions