Artificial Intelligence
Unit – 1
Breadth-First Search (BFS)
Definition
An uninformed (blind) search strategy that expands the shallowest
unexpanded node first, exploring the state space level by level.
Working / Steps
1. Start from the initial state (root node).
2. Place it in a FIFO queue called frontier.
3. Repeatedly remove the first node in the queue.
4. If it is the goal → success.
5. Otherwise, generate all successors and append them to the end of the
queue.
6. Continue until goal is found or queue is empty.
Characteristics
• Completeness: Yes, if the branching factor is finite and a solution exists.
• Optimality: Yes, when all step costs are equal (finds the
shallowest/shortest path).
• Time Complexity: O(b^d)
o b = branching factor
o d = depth of the shallowest goal node.
• Space Complexity: O(b^d) (stores all nodes at the current frontier).
• Advantages: Finds shortest path; simple to implement.
• Disadvantages: Very high memory requirement for large graphs.
Depth-First Search (DFS)
Definition
An uninformed search that expands the deepest unexpanded node first,
exploring as far as possible along a branch before backtracking.
Working / Steps
1. Start from the initial state.
2. Push it onto a stack (or use recursion).
3. Pop the top node.
4. If it is the goal → success.
5. Otherwise, generate successors and push them onto the stack.
6. Continue until goal is found or stack is empty.
Characteristics
• Completeness:
o No, if the search tree is infinite or if loops exist (unless depth limit
is imposed).
• Optimality: No (may find a longer path first).
• Time Complexity: O(b^m)
o m = maximum depth of the state space.
• Space Complexity: O(b·m) (stores only the current path and sibling
nodes).
• Advantages: Low memory use; good when solution is deep and
branching factor is large.
• Disadvantages: May get stuck in infinite paths; not guaranteed to find
shortest path.
Comparison Table
Feature BFS DFS
Data structure Queue (FIFO) Stack (LIFO) / Recursion
Completeness Yes No (unless depth-limited)
Optimality Yes (equal cost) No
Time complexity O(b^d) O(b^m)
Space complexity O(b^d) O(b·m)
Best use When shortest path required When memory is limited
Summary Sentence for Exam
“BFS explores nodes level-wise ensuring the shortest path but at high memory
cost, whereas DFS explores depth-wise using little memory but is neither
complete nor optimal without a depth limit.”
Example Graph
A
/|\
B C D
/\
E F
Goal = F
Start node = A, Goal node = F
Breadth-First Search (BFS)
Expands the shallowest nodes first (level by level).
Steps
Frontier shown as a queue (left = front):
1. Start: [A]
2. Dequeue A → check → not goal → enqueue B, C, D → [B, C, D]
3. Dequeue B → not goal → enqueue E, F → [C, D, E, F]
4. Dequeue C → not goal → [D, E, F]
5. Dequeue D → not goal → [E, F]
6. Dequeue E → not goal → [F]
7. Dequeue F → Goal found.
Order of visit: A, B, C, D, E, F
Path to goal: A → B → F (shortest).
Depth-First Search (DFS)
Goes as deep as possible before backtracking.
Steps
Frontier is a stack (top = left):
1. Start: [A]
2. Pop A → push D, C, B (one common order) → [D, C, B]
3. Pop B → push F, E → [D, C, F, E]
4. Pop E → not goal → [D, C, F]
5. Pop F → Goal found.
Order of visit (one possible): A, B, E, F
Path to goal: A → B → F (not necessarily shortest in other graphs).
Key Takeaways from Example
Feature BFS DFS
Search
Level-wise Depth-wise
pattern
Goal Finds F after exploring all nodes at Finds F as soon as it
discovery depth 1 first reaches B branch
Path
Guaranteed shortest path May or may not be shortest
Optimality
Summary to write in exam
“Given the graph above, BFS visits nodes in order A, B, C, D, E, F and finds the
shortest path A–B–F.
DFS may visit A, B, E, F, finding the goal faster in this case but without the
guarantee of shortest distance in general.”