Depth-First Search (DFS) explores as far as possible along each branch before backtracking.
- Completeness: Yes, when the maximum depth (m) is finite
- Optimality: No, even if step cost is 1
Pseudocode
DepthFirstSearch(Graph, start, goal):
1. Create a stack named fringe list and add (start, path=[start])
2. Create an empty set named expanded to store visited nodes
3. While stack is not empty:
a. Pop the last added node (current, path) from stack (LIFO behavior)
b. If current is the goal, return the path
c. If current is not visited:
i. Add current to visited set
ii. For each neighbor (next) of current in reversed order:
- If next is not visited:
- Add (next, path + [next]) to stack
4. If goal is not found, return failure
Time complexity
Space complexity
Once a node has been expanded, it can be removed from memory as soon as all its descendants have been fully explored.
Back to parent page: Problem Solving and Search