# Depth First Search (DFS) | 4th and 5th Semester | Cognitive Science and AI | BSc.CSIT (TU)

## Depth First Search (DFS) | Fourth and Fifth Semester Second Year | Tribhuvan University (TU) Subject: Cognitive Science and AI | BSc.CSIT

Depth First Search (DFS)
Looks for the goal node among all the children of the current node before using the sibling of this node i.e. expand deepest unexpanded node.

DFS Evaluation

Completeness;

• Does it always find a solution if one exists? :- NO –> If search space is infinite and search space contains loops then DFS may not find solution.

Time complexity;

• Let m is the maximum depth of the search tree. In the worst case Solution may exist at depth m.
• root has b successors, each node at the next level has again b successors (total b2), …
• Worst case; expand all except the last node at depth m
• Total no. of nodes generated:
b + b2 + b3 + ………………….. bm = O(bm)

Space complexity:

• It needs to store only a single path from the root node to a leaf node, along with remaining unexpanded sibling nodes for each node on the path.
• Total no. of nodes in memory:
1+ b + b + b + ………………….. b m times = O(bm)