DFS (Depth First Search) 🎯

Welcome to our comprehensive guide on Depth First Search (DFS)! In this lesson, we'll delve into the world of graph traversal algorithms, focusing on DFS - a powerful technique used in various real-world applications like route finding, network analysis, and more.

Let's start by understanding what DFS is and why we need it.

Understanding DFS 📝

DFS is a method for exploring or searching through a graph, starting at a particular node, and visiting the nodes reachable from that node as far as possible before backtracking. The idea is to explore as deeply as possible along each path before backtracking.

Why DFS? 💡

Connectivity Check: DFS can determine whether two nodes in a graph are connected or not.
Cycle Detection: DFS is used to detect cycles in a graph.
Shortest Path: DFS forms the basis for several algorithms to find the shortest path in a graph, like Dijkstra's and Bellman-Ford algorithms.

DFS Algorithm 📝

The DFS algorithm can be implemented in three main steps:

Initialization: Mark all the vertices as Not Visited. Create a stack and push the current vertex into it.
Exploration: While the stack is not empty, pop a vertex and check if it is visited. If not, mark it as Visited and add all its adjacent vertices to the stack.
Termination: If all the vertices are visited, the graph is completely traversed. If not, repeat the exploration step.

DFS in Action 💡

Let's look at a simple example of DFS implementation in Python.

python

def dfs(vertex, visited, adj_list):
    visited[vertex] = True
    print(vertex, end=" ")

    for neighbor in adj_list[vertex]:
        if not visited[neighbor]:
            dfs(neighbor, visited, adj_list)

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

visited = [False] * len(graph)
dfs('A', visited, graph)
print()

Output:

A B D E C F

In the above example, we have a simple graph and we perform a DFS starting from vertex 'A'. The output shows the order in which the vertices are visited.

DFS Recursion 💡

The above example demonstrates the iterative version of DFS. However, DFS can also be implemented recursively. Let's modify the above example to show the recursive DFS implementation.

python

def dfs_recursive(vertex, visited, adj_list):
    visited[vertex] = True
    print(vertex, end=" ")

    for neighbor in adj_list[vertex]:
        if not visited[neighbor]:
            dfs_recursive(neighbor, visited, adj_list)

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

visited = [False] * len(graph)
dfs_recursive('A', visited, graph)
print()

Output:

A B D E C F

In the recursive version, we avoid the need for a stack, making the code slightly cleaner.

Quiz 📝

With this, we've covered the basics of DFS. As you continue to explore and practice, you'll encounter more complex scenarios and variations of this powerful graph traversal algorithm. Happy coding! 🎉