Depth-First Search (DFS) | Graph Traversal Algorithm

Introduction

Graph is a non-linear data structure that consists of nodes and edges. Depth-first search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. In this challenge, we will implement DFS on a directed graph.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL python(("`Python`")) -.-> python/BasicConceptsGroup(["`Basic Concepts`"]) algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) python(("`Python`")) -.-> python/ControlFlowGroup(["`Control Flow`"]) python(("`Python`")) -.-> python/DataStructuresGroup(["`Data Structures`"]) python(("`Python`")) -.-> python/FunctionsGroup(["`Functions`"]) python(("`Python`")) -.-> python/ModulesandPackagesGroup(["`Modules and Packages`"]) python(("`Python`")) -.-> python/ObjectOrientedProgrammingGroup(["`Object-Oriented Programming`"]) python(("`Python`")) -.-> python/ErrorandExceptionHandlingGroup(["`Error and Exception Handling`"]) python/BasicConceptsGroup -.-> python/comments("`Comments`") algorithm/BasicAlgorithmsGroup -.-> algorithm/graphs_trees("`Graphs Trees`") python/BasicConceptsGroup -.-> python/variables_data_types("`Variables and Data Types`") python/BasicConceptsGroup -.-> python/strings("`Strings`") python/BasicConceptsGroup -.-> python/type_conversion("`Type Conversion`") python/ControlFlowGroup -.-> python/conditional_statements("`Conditional Statements`") python/ControlFlowGroup -.-> python/for_loops("`For Loops`") python/DataStructuresGroup -.-> python/lists("`Lists`") python/DataStructuresGroup -.-> python/tuples("`Tuples`") python/FunctionsGroup -.-> python/function_definition("`Function Definition`") python/FunctionsGroup -.-> python/default_arguments("`Default Arguments`") python/ModulesandPackagesGroup -.-> python/importing_modules("`Importing Modules`") python/ModulesandPackagesGroup -.-> python/using_packages("`Using Packages`") python/ObjectOrientedProgrammingGroup -.-> python/classes_objects("`Classes and Objects`") python/ObjectOrientedProgrammingGroup -.-> python/constructor("`Constructor`") python/ObjectOrientedProgrammingGroup -.-> python/polymorphism("`Polymorphism`") python/ObjectOrientedProgrammingGroup -.-> python/encapsulation("`Encapsulation`") python/ErrorandExceptionHandlingGroup -.-> python/raising_exceptions("`Raising Exceptions`") python/FunctionsGroup -.-> python/build_in_functions("`Build-in Functions`") subgraph Lab Skills python/comments -.-> lab-268827{{"`Depth-First Search on Directed Graphs`"}} algorithm/graphs_trees -.-> lab-268827{{"`Depth-First Search on Directed Graphs`"}} python/variables_data_types -.-> lab-268827{{"`Depth-First Search on Directed Graphs`"}} python/strings -.-> lab-268827{{"`Depth-First Search on Directed Graphs`"}} python/type_conversion -.-> lab-268827{{"`Depth-First Search on Directed Graphs`"}} python/conditional_statements -.-> lab-268827{{"`Depth-First Search on Directed Graphs`"}} python/for_loops -.-> lab-268827{{"`Depth-First Search on Directed Graphs`"}} python/lists -.-> lab-268827{{"`Depth-First Search on Directed Graphs`"}} python/tuples -.-> lab-268827{{"`Depth-First Search on Directed Graphs`"}} python/function_definition -.-> lab-268827{{"`Depth-First Search on Directed Graphs`"}} python/default_arguments -.-> lab-268827{{"`Depth-First Search on Directed Graphs`"}} python/importing_modules -.-> lab-268827{{"`Depth-First Search on Directed Graphs`"}} python/using_packages -.-> lab-268827{{"`Depth-First Search on Directed Graphs`"}} python/classes_objects -.-> lab-268827{{"`Depth-First Search on Directed Graphs`"}} python/constructor -.-> lab-268827{{"`Depth-First Search on Directed Graphs`"}} python/polymorphism -.-> lab-268827{{"`Depth-First Search on Directed Graphs`"}} python/encapsulation -.-> lab-268827{{"`Depth-First Search on Directed Graphs`"}} python/raising_exceptions -.-> lab-268827{{"`Depth-First Search on Directed Graphs`"}} python/build_in_functions -.-> lab-268827{{"`Depth-First Search on Directed Graphs`"}} end

Graph Dfs

Problem

Implement depth-first search on a directed graph. The algorithm should start at a given node and visit all reachable nodes in the graph. The order in which the nodes are visited should be recorded and returned as a list.

Requirements

To implement DFS on a directed graph, the following requirements must be met:

The graph is directed.
Graph and Node classes are already implemented.
The graph is connected.
The inputs are valid.
The algorithm fits memory.

Example Usage

Suppose we have a directed graph with the following edges:

graph.add_edge(0, 1, 5)
graph.add_edge(0, 4, 3)
graph.add_edge(0, 5, 2)
graph.add_edge(1, 3, 5)
graph.add_edge(1, 4, 4)
graph.add_edge(2, 1, 6)
graph.add_edge(3, 2, 7)
graph.add_edge(3, 4, 8)

If we start DFS at node 0, the order of nodes visited should be [0, 1, 3, 2, 4, 5].

Summary

In this challenge, we implemented depth-first search on a directed graph. The algorithm starts at a given node and visits all reachable nodes in the graph. The order in which the nodes are visited is recorded and returned as a list. By meeting the requirements, we can ensure the correctness and efficiency of the algorithm.

Depth-First Search on Directed Graphs