Depth-First Search

Published
Completeness - The graph search variant is complete because it avoids repeated states, redundant paths, and it will eventually visit every node.
The tree search variant is incomplete because it can get stuck in an infinite loop.
Optimality - Not optimal.
Time Complexity - O(bm)
Space Complexity - O(bm)

Visual Example

Current Node Frontier
A B, C
B D, E, C
D E, C
E H, I, C
H I, C
I C
C F, G
F G
G J, K
J K
K
Goal Node Found
  1. We start from the root node A.
  2. We check to see if A is a goal node. It's not, so we add it's children, nodes B and C, to the frontier.
  3. We remove node B from the frontier, we check if it's a goal node. It's not, so we add it's children, nodes D and E, to the frontier.
  4. We remove node D from the frontier, we check if it's a goal node. It's not, so we continue.
  5. We remove node E from the frontier, we check if it's a goal node. It's not, so we add it's children, nodes H and I, to the frontier.
  6. We remove node H from the frontier, we check if it's a goal node. It's not, so we continue.
  7. We remove node I from the frontier, we check if it's a goal node. It's not, so we continue.
  8. We remove node C from the frontier, we check if it's a goal node. It's not, so we add it's children, nodes F and G, to the frontier.
  9. We remove node F from the frontier, we check if it's a goal node. It's not, so we continue.
  10. We remove node G from the frontier, we check if it's a goal node. It's not, so we add it's children, nodes J and K, to the frontier.
  11. We remove node J from the frontier, we check if it's a goal node. It's not, so we continue.
  12. We remove node K from the frontier, we check if it's a goal node. It is, so we're done.

Algorithm Notes


Return to Articles