Iterative Depth-First Search (DFS) using Stack 🎯

Welcome to our deep dive into the world of Iterative Depth-First Search (DFS) using a Stack! This lesson is designed for both beginners and intermediates, so let's start with the basics.

What is Depth-First Search (DFS)? 📝

DFS is an algorithm for traversing or searching tree or graph structures. It starts at the root (or some arbitrary node of the graph) and explores as far as possible along each path before backtracking.

In this lesson, we'll focus on the iterative version of DFS, which uses a stack instead of recursion.

Why use a Stack for DFS? 💡

A stack is a linear data structure that follows the LIFO (Last In First Out) principle. It's ideal for DFS because it helps keep track of the unexplored nodes in the order they were encountered.

DFS using Stack: Algorithm ✅

Create an empty stack s.
Push the start node into the stack s.
While s is not empty:
- Pop a node n from the stack s.
- If n is not visited:
  - Mark n as visited.
  - Traverse all the adjacent nodes of n and push them into the stack s.

Implementing DFS using Stack in Python 📝

Here's a simple example of DFS using a Stack in Python. We'll use an adjacency list to represent the graph.

python

# Graph representation using adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'G'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['E'],
    'G': ['C']
}

def dfs_iterative(graph, start):
    visited = set()
    s = [start]

    while s:
        current = s.pop()
        if current not in visited:
            visited.add(current)
            print(current, end=' ')
            s += graph[current] - visited

    print()

# Start the DFS from node 'A'
dfs_iterative(graph, 'A')

In this example, we start our DFS from node 'A'. The dfs_iterative function maintains a visited set and a stack. It repeatedly pops a node from the stack, marks it as visited, prints it, and adds its unvisited neighbors to the stack.

Practical Applications 💡

DFS with a Stack is useful in various scenarios such as:

Cycle detection in a graph.
Topological Sorting.
Finding the longest path between two nodes.

Iterative Depth-First Search (DFS) using Stack 🎯

Iterative Depth-First Search (DFS) using Stack 🎯

What is Depth-First Search (DFS)? 📝

Why use a Stack for DFS? 💡

DFS using Stack: Algorithm ✅

Implementing DFS using Stack in Python 📝

Practical Applications 💡

Quiz 📝