Skip to main content
Practice

What is Depth First Search (DFS)?

Depth First Search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far along each branch as possible.


Keywords​

  • Stack: DFS uses a stack to keep track of the nodes already visited.

  • Recursion: It can be implemented using recursive function calls, without explicitly using a stack.

  • Pathfinding: DFS is often used to find a path from a start node to a target node.

  • Time Complexity: (O(|V| + |E|)), where (|V|) is the number of vertices and (|E|) is the number of edges.


Step-by-Step Process of DFS​

  1. Select a Node: Choose the node to start the search.

  2. Visit and Explore: Visit the selected node and move to an adjacent unvisited node.

  3. Recursive Exploration: Perform DFS recursively on each node to explore as deep as possible.

  4. Complete Exploration: End the search when there are no more nodes to visit.


Characteristics of DFS​

  • Depth First: Explore each branch completely before moving to another.

  • Backtracking: Return to the previous nodes or paths to explore other options.

  • Non-Cyclic Graphs: DFS is effective in visiting all the nodes in non-cyclic graphs.

  • Traversal Order: The order of node traversal depends on the structure and the start node of the graph.


Advantages and Disadvantages of DFS​

  • Advantages: Simple implementation, guarantees visiting all nodes. It uses relatively less memory.

  • Disadvantages: May not be suitable for finding the shortest path. In graphs with cycles, there is a risk of infinite loops.

Want to learn more?

Join CodeFriends Plus membership or enroll in a course to start your journey.