Search Algorithms in AI: BFS, DFS, UCS and A* Explained on One Worked Graph

Search algorithms often arrive as disconnected recipes: a queue for BFS, a stack for DFS, and a formula for A*. The difficulty starts when one graph asks which path each algorithm returns. One small weighted graph separates them: BFS and greedy best-first return a path costing 13, while uniform-cost search and A* return the cost-8 optimum.

Search as problem formulation

A search problem has five parts: an initial state, actions, a transition model, a goal test, and a path-cost function. States and transitions form the state space. A solution reaches a goal; an optimal solution has minimum path cost.

In the 8-puzzle, states are tile configurations, actions move the blank up, down, left, or right, and moves have unit cost. In route finding, states are cities and cost can be kilometres. A search tree can dwarf its state space because paths repeat states.

We judge completeness, optimality, time, and space. Let b be branching factor, d shallowest goal depth, and m maximum depth. Uninformed search uses only the problem definition; informed search adds h(n), an estimated cost to the goal.

The working graph

Use a directed graph from S to G. Edges are S->A=2, S->B=5, A->B=1, A->C=6, B->C=2, B->G=8, and C->G=3. Heuristics are h(S)=7, h(A)=5, h(B)=4, h(C)=2, and h(G)=0.

The cheapest path is S->A->B->C->G, costing 2+1+2+3=8. The path with the fewest edges is S->B->G, two edges costing 5+8=13. Every algorithm below returns 8 or 13.

Uninformed search: BFS, DFS, UCS and IDDFS

Breadth-first search expands S, then A and B at depth 1. The first goal is generated through B, so BFS returns S->B->G, cost 13. BFS is optimal only when step costs are equal. It finds the fewest edges here, not the cheapest path.

Depth-first search, with alphabetical tie-breaking, follows S->A->B->C->G and returns 8 by luck. Exploring G before C from B would return 11. DFS is neither optimal nor complete in infinite spaces.

Uniform-cost search always expands the lowest accumulated cost g:

UCS is Dijkstra's algorithm run until the goal is removed from the frontier, traced without heuristics in Graph Algorithms: BFS, DFS and Dijkstra Traced Step by Step.

Depth-limited search stops DFS beyond l, but misses a goal at depth d when l<d. Iterative deepening DFS runs limits 0, 1, 2, and onward. It gets BFS-like completeness with DFS-like memory; repeated work is affordable because most nodes lie deepest.

For UCS, C* is optimal cost and e is the minimum positive step cost. In practice, BFS often dies of memory before it dies of time.

Informed search: greedy gets fooled, A* does not

Greedy best-first search expands the smallest h(n). From S, it chooses B because 4 is below h(A)=5; then it chooses G because 0 is below h(C)=2. It returns cost 13. Greedy ignores cost already paid, so it is neither generally complete nor optimal.

A* uses f(n)=g(n)+h(n):

The expanded f values are 7, 7, 7, 7, 8. They never decrease because this heuristic is consistent.

Admissibility means never overestimating the true remaining cost. True costs from S, A, B, C are 8, 6, 5, 3. Their heuristics are 7, 5, 4, 2, each no larger, so h is admissible and tree-search A* is optimal.

Consistency requires h(n) <= c(n,n') + h(n') on every edge. For A->B, 5 <= 1+4; for S->A, 7 <= 2+5. Both are equalities, and the other five edges pass. Thus graph-search A* is optimal without reopening closed nodes.

A* retains generated nodes. IDA* trades repeated work for lower memory. Weighted A* emphasises h for speed while weakening the usual optimality guarantee.

Local search, adversarial search and constraint satisfaction

Local search keeps a current state, not a path or frontier. Hill climbing moves to the best neighbour with constant memory, but stalls at local maxima, plateaus, and ridges. Simulated annealing sometimes accepts worse moves to escape. Both suit 8-queens, scheduling, and optimisation where paths do not matter.

Adversarial search uses minimax for two-player zero-sum games. Alpha-beta pruning keeps the answer while, with perfect ordering, examining about O(b^(m/2)) nodes. Constraint satisfaction treats states as variable assignments, using backtracking and heuristics such as minimum remaining values.

For the logic vocabulary that AI syllabi pair with search, see Propositional and Predicate Logic: Truth Tables to Proofs.

Traps that cost marks

• Writing “BFS is optimal” without a condition. It is optimal with equal step costs. Otherwise use UCS for minimum cost.

• Swapping admissible and consistent. Admissible compares h with true remaining cost at a node. Consistent checks a triangle inequality across every edge. Consistency implies admissibility, but not conversely. Tree-search A* needs admissibility; graph-search A* wants consistency.

• Trusting greedy because it is informed. Informed only means it uses h. Our greedy path costs 13, five more than optimal.

• Computing f only at the goal. Maintain g along every path, update it when a cheaper route appears, then add h.

• Ignoring space. BFS uses O(b^d) space, while IDDFS uses O(bd).

• Counting nodes instead of edge costs. S->A->B->C->G has four edges whose costs sum to 8.

How exams and interviews test search

Use the working graph as a four-question drill. Greedy returns S->B->G, cost 13. UCS expands S, A, B, C, G. The heuristic is admissible because 7<=8, 5<=6, 4<=5, and 2<=3. A* returns cost 8. NAT-style questions often ask for one of these final numbers.

Search sits in the artificial intelligence section of the GATE Data Science and AI syllabus, alongside adversarial search and logic, and the topic also appears in UGC NET Computer Science, university, teaching-recruitment and placement papers. Check the conducting body's official website for the current syllabus and paper structure. An algorithms paper tests BFS, DFS and Dijkstra as graph algorithms with no heuristic at all, so the same three names carry different expectations in the two papers.

Interviewers ask when A* beats Dijkstra. A useful h focuses expansion; with h=0, A* becomes UCS or Dijkstra. A suboptimal result suggests an overestimating heuristic. For AI-focused rounds, continue with AI & ML for Placements | Generative AI Placement Course.

The short version and the next step

Problem formulation gives states, actions, goals, and costs. On our graph, BFS and greedy return 13, while UCS and A* return 8. Admissibility protects A* optimality, consistency produces the nondecreasing f sequence 7, 7, 7, 7, 8, and IDDFS offers BFS-like completeness with much lower memory.

For structured preparation, use GATE Guidance by Sanchit Sir. For interview-style practice across core CS subjects, see Technical Interview Prep: OS, DBMS, CN and OOP Answers.