top of page

Learn through our Blogs, Get Expert Help & Innovate with Colabcodes

Welcome to Colabcodes, where technology meets innovation. Our articles are designed to provide you with the latest news and information about the world of tech. From software development to artificial intelligence, we cover it all. Stay up-to-date with the latest trends and technological advancements. If you need help with any of the mentioned technologies or any of its variants, feel free to contact us and connect with our freelancers and mentors for any assistance and guidance. 

blog cover_edited.jpg

ColabCodes

Writer's picturesamuel black

Implementing Depth-First Search (DFS) Algorithm in Python

In this blog, we'll walk through the implementation of Depth-First Search (DFS) in Python, covering both recursive and iterative approaches. We'll use an adjacency list representation for our graph, which is a common way to represent graphs in Python.

Depth-First Search (DFS) Algorithm in Python

What is Depth-First Search (DFS) Algorithm?

Depth-First Search (DFS) is a classic algorithm used for traversing or searching tree and graph data structures. Unlike Breadth-First Search (BFS), which explores nodes level by level, DFS explores as far down a branch as possible before backtracking. This approach can be particularly useful for tasks like pathfinding, topological sorting, and solving puzzles.


Prerequisites

Before we dive into the code, ensure you have a basic understanding of graph theory and Python programming. If you're new to graphs, it's helpful to know that a graph is made up of nodes (vertices) and edges connecting them.


Graph Representation

We'll start by representing our graph using an adjacency list. In Python, an adjacency list can be implemented using a dictionary where keys represent nodes and values are lists of adjacent nodes.


# Graph representation using an adjacency list

graph = {

    'A': ['B', 'C'],

    'B': ['A', 'D', 'E'],

    'C': ['A', 'F'],

    'D': ['B'],

    'E': ['B', 'F'],

    'F': ['C', 'E']

}

Depth-First Search (DFS) Algorithm in Python

Depth-First Search (DFS) in Python is a classic graph traversal algorithm used to explore nodes and edges of a graph by diving as deep as possible into the graph before backtracking. Starting from a given source node, DFS explores each branch of the graph recursively or iteratively until it reaches the end of a branch. In Python, DFS can be implemented using either recursion or a stack data structure. When using recursion, the algorithm visits a node, processes it, and then recursively visits all its unvisited neighbors. If implemented iteratively, a stack is used to manage the nodes to be explored, pushing each unvisited neighbor onto the stack as it traverses the graph. DFS is particularly useful for tasks such as finding connected components, solving puzzles, and topological sorting. Its ability to explore deeply and backtrack efficiently makes it a valuable algorithm for various computational problems in Python.


Recursive Depth-First Search (DFS) Algorithm in Python Implementation

The recursive approach to DFS is elegant and straightforward. The idea is to explore each branch of the graph recursively, marking nodes as visited to avoid cycles.


def dfs_recursive(graph, node, visited=None):

     if visited is None:

         visited = set()

    

     # Mark the node as visited

     visited.add(node)

     print(node, end=' ')

    

     # Explore each adjacent node

     for neighbor in graph[node]:

         if neighbor not in visited:

             dfs_recursive(graph, neighbor, visited)

    

     return visited


# Run DFS starting from node 'A'

print("DFS (Recursive):")

dfs_recursive(graph, 'A')


Output of the code above:

DFS (Recursive):
A B D E F C 
{'A', 'B', 'C', 'D', 'E', 'F'}

Iterative Depth-First Search (DFS) Algorithm in Python Implementation

The iterative approach uses a stack to manage the nodes to be explored. This method avoids the recursion limit issues of the recursive approach, making it suitable for large graphs.


def dfs_iterative(graph, start):

     visited = set()

     stack = [start]

    

     while stack:

        node = stack.pop()

         if node not in visited:

             visited.add(node)

             print(node, end=' ')

             # Add all unvisited neighbors to the stack

             stack.extend(neighbor for neighbor in graph[node] if neighbor not in  visited)

    

     return visited


# Run DFS starting from node 'A'

print("\nDFS (Iterative):")

dfs_iterative(graph, 'A')


Output of the code above:

DFS (Iterative):
A C F E B D 
{'A', 'B', 'C', 'D', 'E', 'F'}

Explanations for the code above:


Recursive Depth-First Search


  • Base Case: The function first checks if the visited set is None and initializes it if needed.

  • Visit Node: It marks the current node as visited and prints it.

  • Recursive Call: For each unvisited neighbor, the function recursively calls itself.


Iterative Depth-First Search


  • Initialization: It uses a stack to keep track of nodes to be visited and a set to track visited nodes.

  • Loop: It pops nodes from the stack, marks them as visited, and pushes their unvisited neighbors onto the stack.


Advantages and Use Cases

  • Recursive DFS: Simple and easy to implement, ideal for smaller graphs and scenarios where recursion depth is not a concern.

  • Iterative DFS: More robust for larger graphs and avoids potential issues with recursion limits.


Conclusion

Depth-First Search (DFS) is a versatile and essential algorithm for graph traversal. By understanding both recursive and iterative implementations, you can choose the approach that best suits your needs based on the size of the graph and specific use cases. Whether you're exploring networks, solving puzzles, or analyzing data, DFS is a powerful tool in your programming arsenal.

Related Posts

See All

Comments


Get in touch for customized mentorship and freelance solutions tailored to your needs.

bottom of page