Interview Prep
Career
GenAI
Prompt Engg
ChatGPT
LLM
Langchain
RAG
AI Agents
Machine Learning
Deep Learning
GenAI Tools
LLMOps
Python
NLP
SQL
AIML Projects

Reading list

Machine Learning Basics for a Newbie
6 Steps of Machine learning Lifecycle Introduction to Predictive Modeling
Introduction to Exploratory Data Analysis & Data Insights Descriptive Statistics Inferential Statistics How to Understand Population Distributions?
Reading Data Files into Python Different Variable Datatypes
Probability for Data Science Basic Concepts of Probability Axioms of Probability Conditional Probability
Central Tendencies for Continuous Variables Spread of Data KDE plots for Continuous Variable Overview of Distribution for Continuous variables Normal Distribution Skewed Distribution Skeweness and Kurtosis Distribution for Continuous Variable
Central Tendencies for Categorical Variables Understanding Discrete Distributions Performing EDA on Categorical Variables
Dealing with Missing Values Understanding Outliers Identifying Outliers in Data Outlier Detection in Python Outliers Detection Using IQR, Z-score, LOF and DBSCAN
Sample and Population Central Limit Theorem Confidence Interval and Margin of Error
Bivariate Analysis Introduction
Covariance Pearson Correlation Spearman's Correlation & Kendall's Tau Correlation versus Causation Tabular and Graphical methods for Bivariate Analysis Performing Bivariate Analysis on Continuous-Continuous Variables
Tabular and Graphical methods for Continuous-Categorical Variables Introduction to Hypothesis Testing P-value Two sample Z-test T-test T-test vs Z-test Performing Bivariate Analysis on Continuous-Catagorical variables
Chi-Squares Test Bivariate Analysis on Categorical Categorical Variables
Multivariate Analysis A Comprehensive Guide to Data Exploration The Data Science behind IPL
Supervised Learning vs Unsupervised Learning Reinforcement Learning Generative and Descriminative Models Parametric and Non Parametric model
Machine Learning Pipeline Preparing Dataset Build a Benchmark Model: Regression Build a Benchmark Model: Classification
Evaluation Metrics for Machine Learning Everyone should know Confusion Matrix Accuracy Precision and Recall AUC-ROC Log Loss R2 and Adjusted R2
Dealing with Missing Values Replacing Missing Values Imputing Missing Values in Data Working with Categorical Variables Working with Outliers Preprocessing Data for Model Building
Understanding Cost Function Understanding Gradient Descent Math Behind Gradient Descent Assumptions of Linear Regression Implement Linear Regression from Scratch Train Linear Regression in Python Implementing Linear Regression in R Diagnosing Residual Plots in Linear Regression Models Generalized Linear Models Introduction to Logistic Regression Odds Ratio Implementing Logistic Regression from Scratch Introduction to Scikit-learn in Python Train Logistic Regression in python Multiclass using Logistic Regression How to use Multinomial and Ordinal Logistic Regression in R ? Challenges with Linear Regression Introduction to Regularisation Implementing Regularisation Ridge Regression Lasso Regression
Introduction to K Nearest Neighbours Determining the Right Value of K in KNN Implement KNN from Scratch Implement KNN in Python
Bias Variance Tradeoff Introduction to Overfitting and Underfitting Visualizing Overfitting and Underfitting Selecting the Right Model What is Validation? Hold-Out Validation Understanding K Fold Cross Validation
Introduction to Feature Selection Feature Selection Algorithms Missing Value Ratio Low Variance Filter High Correlation Filter Backward Feature Elimination Forward Feature Selection Implement Feature Selection in Python Implement Feature Selection in R
Introduction to Decision Tree Purity in Decision Tree Terminologies Related to Decision Tree How to Select Best Split Point in Decision Tree? Chi-Squares Information Gain Reduction in Variance Optimizing Performance of Decision Tree Train Decision Tree using Scikit Learn Pruning of Decision Trees
Introduction to Feature Engineering Feature Transformation Feature Scaling Feature Engineering Frequency Encoding Automated Feature Engineering: Feature Tools
Introduction to Naive Bayes Conditional Probability and Bayes Theorem Introduction to Bayesian Adjustment Rating: The Incredible Concept Behind Online Ratings! Working of Naive Bayes Math behind Naive Bayes Types of Naive Bayes Implementation of Naive Bayes
Understanding how to solve Multiclass and Multilabled Classification Problem Evaluation Metrics: Multi Class Classification
Introduction to Ensemble Techniques Basic Ensemble Techniques Implementing Basic Ensemble Techniques Finding Optimal Weights of Ensemble Learner using Neural Network Why Ensemble Models Work well?
Introduction to Stacking Implementing Stacking Variants of Stacking Implementing Variants of Stacking Introduction to Blending Bootstrap Sampling Introduction to Random Sampling Hyper-parameters of Random Forest Implementing Random Forest Out-of-Bag (OOB) Score in the Random Forest IPL Team Win Prediction Project Using Machine Learning Introduction to Boosting Gradient Boosting Algorithm Math behind GBM Implementing GBM in python Regularized Greedy Forests Extreme Gradient Boosting Implementing XGBM in python Tuning Hyperparameters of XGBoost in Python Implement XGBM in R/H2O Adaptive Boosting Implementing Adaptive Boosing LightGBM Implementing LightGBM in Python Catboost Implementing Catboost in Python
Different Hyperparameter Tuning methods Implementing Different Hyperparameter Tuning methods GridsearchCV RandomizedsearchCV Bayesian Optimization for Hyperparameter Tuning Hyperopt
Understanding SVM Algorithm SVM Kernels In-depth Intuition and Practical Implementation SVM Kernel Tricks Kernels and Hyperparameters in SVM Implementing SVM from Scratch in Python and R
Introduction to Principal Component Analysis Steps to Perform Principal Compound Analysis Computation of Covariance Matrix Finding Eigenvectors and Eigenvalues Implementing PCA in python Visualizing PCA A Brief Introduction to Linear Discriminant Analysis Introduction to Factor Analysis
Introduction to Clustering Applications of Clustering Evaluation Metrics for Clustering Understanding K-Means Implementation of K-Means in Python Implementation of K-Means in R Choosing Right Value for K Profiling Market Segments using K-Means Clustering Hierarchical Clustering Implementation of Hierarchial Clustering DBSCAN Defining Similarity between clusters Build Better and Accurate Clusters with Gaussian Mixture Models
Understand Basics of Recommendation Engine with Case Study
8 Ways to Improve Accuracy of Machine Learning Models
Introduction to Dask Working with CuML
Introduction to Machine Learning Interpretability Framework and Interpretable Models model Agnostic Methods for Interpretability Implementing Interpretable Model Understanding SHAP Out-of-Core ML Introduction to Interpretable Machine Learning Models Model Agnostic Methods for Interpretability Game Theory & Shapley Values
Introduction to Machine Learning Interpretability Framework and Interpretable Models model Agnostic Methods for Interpretability Implementing Interpretable Model Understanding SHAP Out-of-Core ML Introduction to Interpretable Machine Learning Models Model Agnostic Methods for Interpretability Game Theory & Shapley Values
Introduction to AutoML Implementation of MLBox Introduction to PyCaret TPOT Auto-Sklearn EvalML
Pickle and Joblib Introduction to Model Deployment
Deploying Machine Learning Model using Streamlit Deploying ML Models in Docker Deploy Using Streamlit Deploy on Heroku Deploy Using Netlify Introduction to Amazon Sagemaker Setting up Amazon SageMaker Using SageMaker Endpoint to Generate Inference Deploy on Microsoft Azure Cloud Introduction to Flask for Model Deploying ML model using Flask
Model Deployment in Android Model Deployment in Iphone

Implementation of Depth First Search (DFS) Algorithm in Python

NISHANT TIWARI
NISHANT TIWARI Last Updated : 05 Jun, 2024
5 min read

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.

Depth First Search (DFS)

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.

Table of contents

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

Q1. What is the main purpose of using DFS in graph traversal?

A. The primary goal of DFS is to traverse all the nodes in a graph, visiting each node exactly once (which means no node is visited twice or more), while recursively visiting as deep as possible along a branch before backtracking.

Q2. Why might one prefer the iterative implementation of DFS over the recursive one?

A. DFS can be implemented using recursion, but iterative implementation is desired, especially where the stack is limited, or the recursion depth limit is not high, to prevent stack overflow.

Q3. How does DFS handle cycles in a graph?

A. DFS handles cycles by keeping track of visited nodes, ensuring each node is visited only once to prevent infinite loops.

Q4. Can DFS be used to find the shortest path in a graph?

A. DFS does not guarantee the shortest path in an unweighted graph; Breadth-First Search (BFS) is better suited for this purpose.

NISHANT TIWARI
NISHANT TIWARI

Seasoned AI enthusiast with a deep passion for the ever-evolving world of artificial intelligence. With a sharp eye for detail and a knack for translating complex concepts into accessible language, we are at the forefront of AI updates for you. Having covered AI breakthroughs, new LLM model launches, and expert opinions, we deliver insightful and engaging content that keeps readers informed and intrigued. With a finger on the pulse of AI research and innovation, we bring a fresh perspective to the dynamic field, allowing readers to stay up-to-date on the latest developments.

Free Courses

Generative AI 4.7

Generative AI - A Way of Life

Explore Generative AI for beginners: create text and images, use top AI tools, learn practical skills, and ethics.
Large Language Models 4.5

Getting Started with Large Language Models

Master Large Language Models (LLMs) with this course, offering clear guidance in NLP and model training made simple.
Prompt Engineering 4.6

Building LLM Applications using Prompt Engineering

This free course guides you on building LLM apps, mastering prompt engineering, and developing chatbots with enterprise data.
LlamaIndex 4.8

Improving Real World RAG Systems: Key Challenges & Practical Solutions

Explore practical solutions, advanced retrieval strategies, and agentic RAG systems to improve context, relevance, and accuracy in AI-driven applications.
RAG systems using LlamaIndex 4.7

Microsoft Excel: Formulas & Functions

Master MS Excel for data analysis with key formulas, functions, and LookUp tools in this comprehensive course.

Recommended Articles

Responses From Readers

Clear

Write for us

Write, captivate, and earn accolades and rewards for your work
  • Reach a Global Audience
  • Get Expert Feedback
  • Build Your Brand & Audience
  • Cash In on Your Knowledge
  • Join a Thriving Community
  • Level Up Your Data Science Game
imag

We use cookies essential for this site to function well. Please click to help us improve its usefulness with additional cookies. Learn about our use of cookies in our Privacy Policy & Cookies Policy.

Show details