DFS Algorithm
What is DFS?
• DFS = Depth First Search
• Graph/tree traversal algorithm
• Explores as deep as possible along a branch before backtracking
• Uses stack (explicitly or via recursion)
Properties of BFS
• Traverses graph deep-first
• Backtracks when no further node is available
• Suitable for pathfinding, topological sorting, maze solving
• May not always find the shortest path (unlike BFS)
DFS Algorithm (Steps)
1. Start at the source node.
2. Mark it as visited.
3. Push it onto a stack (or recursive call).
4. Visit an unvisited neighbor.
5. Repeat until no neighbors left.
6. Backtrack and continue with other unvisited nodes.
Initial Node : A
Goal Node : G
Advantage & Disadvantages of DFS
Applications of DFS in AI
• Pathfinding – explore state spaces like mazes, 8-puzzle.
• Game playing – used in game trees (Tic-Tac-Toe, Chess) with minimax.
• Planning – decomposing problems into subproblems.
• Cycle detection – avoid loops in graphs or reasoning systems.
• Web crawling – deep traversal of linked pages.
• Constraint satisfaction problems (CSPs) – backtracking in Sudoku, N-
Queens, etc.
• Natural Language Processing – parsing sentences into syntax trees.
• Knowledge representation & reasoning – traversing semantic networks,
decision trees.
Key BFS DFS
Definition BFS stands for Breadth First Search. DFS stands for Depth First Search.
Data structure BFS uses a Queue to find the shortest DFS uses a Stack to find the shortest
path. path.
Source BFS is better when target is closer to DFS is better when target is far from
Source. source.
DFS is more suitable for decision tree.
Suitability for decision As BFS considers all neighbor so it is As with one decision, we need to
tree not suitable for decision tree used in traverse further to augment the
puzzle games. decision. If we reach the conclusion,
we won.
Speed BFS is slower than DFS. DFS is faster than BFS.
Time Complexity of BFS = O(V+E) Time Complexity of DFS is also O(V+E)
Time Complexity where V is vertices and E is edges. where V is vertices and E is edges.
Memory BFS requires more memory space. DFS requires less memory space.
In BFS, there is no problem of In DFS, we may be trapped into
Tapping in loops trapping into finite loops. infinite loops.
BFS is implemented using FIFO (First DFS is implemented using LIFO (Last
Principle In First Out) principle. In First Out) principle.