Uninformed Search Strategies: BFS, DFS, UCS and a Worked Graph

Memorising BFS, DFS and UCS as queue, stack and priority queue breaks when a question asks for expansion order, changes costs, or distinguishes shallowest from cheapest. A single weighted graph distinguishes BFS, DFS and UCS by expansion order and cost, followed by checks of DLS, IDDFS and bidirectional search.

What makes a search strategy uninformed

A search problem specifies states, start, successors, transitions, goal test and step costs. Each node records state, parent, action, depth and accumulated cost g(n).

An uninformed strategy uses no goal-directed estimate such as h(n). It may use successors, depth or exact paid costs. BFS favours depth, DFS recency, and UCS minimum g(n), so UCS remains uninformed.

A state is not a path. Different parents may reach it at different costs, so graph search needs duplicate handling and UCS needs relaxation. Review Graph Algorithms: BFS, DFS and Shortest Paths, or place the topic in the wider GATE CS exam preparation courses route.

BFS, DFS, DLS, IDDFS, UCS and bidirectional search at a glance

For complexity, b is branching factor, d shallowest solution depth, m maximum depth, l limit, C* optimal cost, and epsilon a positive step-cost lower bound. Formulas need these assumptions.

Use BFS or IDDFS for shallow equal-cost solutions, UCS for least cost, DFS for tight memory, DLS with a defensible bound, and bidirectional search when reverse expansion works.

Weighted-graph traces for BFS, DFS, DLS, IDDFS, UCS and bidirectional search

Use nodes S, A, B, D, E, G, start S and goal G. Edges are S->A:1, S->B:5, A->E:6, A->D:1, B->G:8, B->E:1, E->G:1 and D->G:6. There are no others.

Successor order is S:[A,B], A:[E,D], B:[G,E], E:[G], D:[G]. BFS uses that order; DFS pushes it in reverse. Test goals on removal. BFS and DFS mark discovery on insertion. UCS tracks best g, relaxes improvements and settles states on their cheapest pop.

The complete routes are:

• S-B-G: depth 2, cost 5+8=13

• S-A-E-G: depth 3, cost 1+6+1=8

• S-A-D-G: depth 3, cost 1+1+6=8

• S-B-E-G: depth 3, cost 5+1+1=7

Thus S-B-G is uniquely shallowest, while S-B-E-G is uniquely cheapest.

Worked example: trace BFS, DFS and UCS step by step

The BFS queue starts with [S]:

BFS expands S,A,B,E,D,G, returning depth 2, cost 13.

For DFS, stack top is left: [S] -> [A,B] after pop S, push B then A; [E,D,B] after pop A, push D then E; [G,D,B] after pop E, push G. Pop G. DFS expands S,A,E,G, returning S-A-E-G, depth 3, cost 1+6+1=8. Successor order can change its path.

For UCS, [S:0] becomes [A:1,B:5]. Pop A: [D:2,B:5,E:7]. Pop D: [B:5,E:7,G:8]. Pop B; reject G:13, replace E:7 by E:6, and change E’s parent from A to B. Pop E; replace G:8 by G:7, and change G’s parent from D to E. Pop G and reconstruct G<-E<-B<-S. Settled order: S,A,D,B,E,G. Result: S-B-E-G, cost 7.

Depth limits, iterative deepening and meeting in the middle

With root depth 0, DLS limit l=2 visits S(0), A(1), E(2 cutoff), D(2 cutoff), B(1), G(2 goal), returning S-B-G, cost 13. At l=1, it visits S,A,B and returns cutoff, not failure, because deeper successors exist.

IDDFS examines [S], then [S,A,B], then [S,A,E,D,B,G] at limits 0, 1 and 2. That is 1+3+6=10 visits. Repetition trades time for DFS-like memory and still finds the shallowest depth-2 path.

Bidirectional BFS expands from S to {A,B} and backward from G to predecessors {B,E,D}. Meeting at B reconstructs S-B-G. It is shallowest but costs 13, above the cost-7 three-edge route. Weighted bidirectional search needs separate priorities and stopping rules.

Common uninformed-search traps and their exact corrections

• Calling BFS cheapest: BFS costs 13; UCS costs 7. Choose fewest edges or minimum cost.

• Reading drawing order as DFS order: to visit [A,B], push B before A. Record the stack.

• Stopping UCS at goal generation: D gives G:8; E improves it to G:7. Accept G on pop.

• Freezing the first path: B improves E from 7 to 6. Use best_g, improved records and stale-record checks.

• Treating cutoff as failure: DLS at l=1 has not proved G unreachable. Distinguish all three outcomes.

• Dropping assumptions: DFS can follow an infinite branch, UCS needs suitable costs, and reverse search needs predecessors.

How questions test uninformed search strategies

Common tasks compute expansion order, reconstruct parents, separate depth from cost, match guarantees, or change costs, goal timing and limits.

Six quick checks: BFS gives G parent B; BFS costs 13, not 7; DFS expands S,A,E,G; UCS improves E from 7 to 6; UCS improves G from 8 to 7; IDDFS makes 10 visits and returns depth 2.

Change only B->G from 8 to 1. BFS and IDDFS keep their path, now 5+1=6. UCS also returns it because 6 beats the unchanged route costing 7. Only cost changed UCS priority.

These strategies never estimate remaining distance. Ranking by h(n) or g(n)+h(n) is informed. Search Algorithms in Artificial Intelligence: Complete Guide connects uninformed methods to informed, local, adversarial and constraint-satisfaction search. For uninformed-search calculations, redraw the exact frontier states, cutoffs and relaxations above.

Uninformed search strategies: the short version and next step

Choose BFS for shallowest equal-cost paths, DFS when memory matters, DLS for a justified bound, IDDFS for shallow solutions with DFS-like memory, UCS for minimum cost, and bidirectional search when reverse expansion works.

BFS returns S-B-G, depth 2, cost 13; DFS returns S-A-E-G, cost 8; UCS returns S-B-E-G, cost 7. Redraw the frontiers and both relaxations. KnowledgeGate has 3+ live practice questions on Uninformed Search Strategies for focused practice.

Continue with GATE Guidance by Sanchit Sir for structured core CS, or AI & ML for Placements for practical AI.