Skip to main content

Depth-First Search (DFS) Algorithm Explained with Examples and Applications

 What is Depth-First Search (DFS)?

Depth-First Search (DFS) is a fundamental algorithm for traversing or searching tree and graph data structures. The algorithm explores as far as possible along each branch before backtracking, making it suitable for pathfinding, topological sorting, and cycle detection tasks.

DFS Algorithm Explanation

DFS can be implemented using either recursion (implicit call stack) or an explicit stack data structure. The core idea is:

  • Start at the root (or any arbitrary node for a graph).
  • Visit a node and mark it as visited.
  • Recursively or iteratively visit all the adjacent unvisited nodes.

Algorithm Steps (for Binary Tree - Recursive)

  1. Visit the current node.
  2. Recursively traverse the left subtree.
  3. Recursively traverse the right subtree.

Algorithm Steps (for General Graph - Iterative with Stack)

  1. Push the start node onto the stack and mark it as visited.
  2. While the stack is not empty:
    • Pop a node from the stack.
    • Process the node.
    • Push all unvisited adjacent nodes onto the stack and mark them visited.

Python Example Code

1. DFS for Binary Tree (Recursive)

class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None

def dfs_binary_tree(node):
    if not node:
        return
    print(node.val)
    dfs_binary_tree(node.left)
    dfs_binary_tree(node.right)

# Example Usage
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

dfs_binary_tree(root)

Output:

1
2
4
5
3

2. DFS for General Graph (Iterative)

def dfs_graph(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node)
            visited.add(node)
            # Push neighbors in reverse order for correct traversal
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

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

dfs_graph(graph, 'A')

Output:

A
B
D
E
F
C

Time and Space Complexity Analysis

Binary Tree

  • Time Complexity: $O(n)$ where $n$ is the number of nodes. Each node is visited exactly once.
  • Space Complexity: $O(h)$ where $h$ is the height of the tree (due to recursion stack).

General Graph

  • Time Complexity: $O(V + E)$ where $V$ is the number of vertices and $E$ is the number of edges.
  • Space Complexity: $O(V)$ to store the visited nodes and the recursion or stack.

Conclusion

Depth-First Search is a versatile and powerful tool in algorithm design. It is particularly effective when the solution involves deep paths, recursion, or backtracking. A deep understanding of DFS is crucial for solving a wide variety of algorithmic problems efficiently.

References

Tags

Comments

Post a Comment

Popular

How to Fine-Tune LLaMA 3.2-1B-Instruct for Korean Instruction Tasks with LoRA and Hugging Face

LLaMA 3.2-1B-Instruct is a lightweight instruction-tuned language model released by Meta. It is designed to handle a wide range of instruction-based tasks with relatively low computational resources. Although the model was trained with multilingual capabilities, its performance on languages not included in its training set—such as Korean—is limited. This tutorial demonstrates how to fine-tune this open-source model on a Korean dataset using Hugging Face Transformers and PEFT (specifically LoRA), enabling it to better respond to Korean instructions. 1. Prerequisites Before running the example code below, ensure you have the following libraries installed: pip install torch transformers datasets peft accelerate mlflow huggingface_hub To use the LLaMA model or KoAlpaca datasets, you'll need a Hugging Face token. Additionally, you may need to handle potential CUDA Out-Of-Memory (OOM) errors. The following code takes care of both: from huggingface_hub import login login("y...
Post a Comment
Read more

RF-DETR: Overcoming the Limitations of DETR in Object Detection

RF-DETR (Region-Focused DETR), proposed in April 2025, is an advanced object detection architecture designed to overcome fundamental drawbacks of the original DETR (DEtection TRansformer) . In this technical article, we explore RF-DETR's contributions, architecture, and how it compares with both DETR and the improved model D-FINE . We also provide experimental benchmarks and discuss its real-world applicability. RF-DETR Architecture diagram for object detection Limitations of DETR DETR revolutionized object detection by leveraging the Transformer architecture, enabling end-to-end learning without anchor boxes or NMS (Non-Maximum Suppression). However, DETR has notable limitations: Slow convergence, requiring heavy data augmentation and long training schedules Degraded performance on low-resolution objects and complex scenes Lack of locality due to global self-attention mechanisms Key Innovations in RF-DETR RF-DETR intr...
Post a Comment
Read more

Using Gemini API in LangChain: Step-by-Step Tutorial

What is LangChain and Why Use It? LangChain  is an open-source framework that simplifies the use of  Large Language Models (LLMs)  like OpenAI, Gemini (Google), and others by adding structure, tools, and memory to help build real-world applications such as chatbots, assistants, agents, or AI-enhanced software. Why Use LangChain for LLM Projects? Chainable Components : Easily build pipelines combining prompts, LLMs, tools, and memory. Multi-Model Support : Work with Gemini, OpenAI, Anthropic, Hugging Face, etc. Built-in Templates : Manage prompts more effectively. Supports Multi-Turn Chat : Manage complex interactions with memory and roles. Tool and API Integration : Let the model interact with external APIs or functions. Let's Walk Through the Code: Gemini + LangChain I will break the code into  4 main parts , each showcasing different features of LangChain and Gemini API. Part 1: Basic Gemini API Call Using LangChain import os from dotenv import load_dotenv load_dot...
Post a Comment
Read more