Uninformed (blind) strategies know nothing about where the goal is — only how to generate successors and test for the goal. They differ solely in which frontier node to expand next.

Strategy	Frontier	Expands	Finds
Breadth-first (BFS)	FIFO queue	Shallowest node first — level by level	The path with the fewest steps
Depth-first (DFS)	LIFO stack (or recursion)	Deepest node first	Some path — often long
Uniform-cost (UCS)	Priority queue on path cost `g(n)`	Cheapest-so-far node first	The lowest-cost path (Dijkstra's algorithm)

BFS and DFS on the Romania map

The classic textbook example: drive from Arad to Bucharest. Roads have lengths in km; the neighbour order below is the order roads were listed.

Python

ROADS = """Arad Zerind 75, Arad Sibiu 140, Arad Timisoara 118, Zerind Oradea 71, Oradea Sibiu 151,
Timisoara Lugoj 111, Lugoj Mehadia 70, Mehadia Drobeta 75, Drobeta Craiova 120, Craiova Rimnicu 146,
Craiova Pitesti 138, Sibiu Fagaras 99, Sibiu Rimnicu 80, Rimnicu Pitesti 97, Fagaras Bucharest 211,
Pitesti Bucharest 101, Bucharest Giurgiu 90, Bucharest Urziceni 85, Urziceni Hirsova 98,
Hirsova Eforie 86, Urziceni Vaslui 142, Vaslui Iasi 92, Iasi Neamt 87"""
graph = {}                                  # city -> {neighbour: road km}  ("Rimnicu" = Rimnicu Vilcea)
for road in ROADS.split(","):
    a, b, km = road.split()
    graph.setdefault(a, {})[b] = int(km)
    graph.setdefault(b, {})[a] = int(km)

from collections import deque

def path(parent, node):
    out = []
    while node:
        out.append(node)
        node = parent[node]
    return out[::-1]

def bfs(start, goal):
    frontier, parent, expanded = deque([start]), {start: None}, 0
    while frontier:
        node = frontier.popleft()                     # FIFO: oldest node first
        expanded += 1
        for nbr in graph[node]:
            if nbr not in parent:
                parent[nbr] = node
                if nbr == goal:                       # BFS may test the goal when a node is generated
                    return path(parent, nbr), expanded
                frontier.append(nbr)

def dfs(start, goal):
    frontier, parent, expanded = [start], {start: None}, 0
    while frontier:
        node = frontier.pop()                         # LIFO: newest node first
        if node == goal:
            return path(parent, node), expanded
        expanded += 1
        for nbr in graph[node]:
            if nbr not in parent:
                parent[nbr] = node
                frontier.append(nbr)

def cost(route):
    return sum(graph[a][b] for a, b in zip(route, route[1:]))

route, n = bfs("Arad", "Bucharest")
print(route, cost(route), n)     # ['Arad', 'Sibiu', 'Fagaras', 'Bucharest'] 450 6
route, n = dfs("Arad", "Bucharest")
print(route, cost(route), n)     # ['Arad', 'Timisoara', 'Lugoj', 'Mehadia', 'Drobeta', 'Craiova', 'Pitesti', 'Bucharest'] 733 7

BFS finds the route with the fewest roads (3), but it is not the shortest in km. DFS dives down whichever branch it pushed last and returns a much longer route.

Uniform-cost search

UCS always expands the frontier node with the lowest path cost g(n). It must test for the goal when a node is popped, not when it is generated — a cheaper route to the goal may still be on the frontier.

Python

ROADS = """Arad Zerind 75, Arad Sibiu 140, Arad Timisoara 118, Zerind Oradea 71, Oradea Sibiu 151,
Timisoara Lugoj 111, Lugoj Mehadia 70, Mehadia Drobeta 75, Drobeta Craiova 120, Craiova Rimnicu 146,
Craiova Pitesti 138, Sibiu Fagaras 99, Sibiu Rimnicu 80, Rimnicu Pitesti 97, Fagaras Bucharest 211,
Pitesti Bucharest 101, Bucharest Giurgiu 90, Bucharest Urziceni 85, Urziceni Hirsova 98,
Hirsova Eforie 86, Urziceni Vaslui 142, Vaslui Iasi 92, Iasi Neamt 87"""
graph = {}                                  # city -> {neighbour: road km}  ("Rimnicu" = Rimnicu Vilcea)
for road in ROADS.split(","):
    a, b, km = road.split()
    graph.setdefault(a, {})[b] = int(km)
    graph.setdefault(b, {})[a] = int(km)

import heapq

def ucs(start, goal):
    frontier = [(0, start)]                           # (path cost g, city)
    best, parent, expanded = {start: 0}, {start: None}, []
    while frontier:
        g, node = heapq.heappop(frontier)
        if node == goal:                              # goal test on expansion → optimal
            route = [node]
            while parent[route[-1]]:
                route.append(parent[route[-1]])
            return route[::-1], g, expanded
        if g > best[node]:
            continue                                  # stale entry: a cheaper path was found later
        expanded.append(node)
        for nbr, km in graph[node].items():
            if g + km < best.get(nbr, float("inf")):
                best[nbr], parent[nbr] = g + km, node
                heapq.heappush(frontier, (g + km, nbr))

route, g, expanded = ucs("Arad", "Bucharest")
print(route, g)          # ['Arad', 'Sibiu', 'Rimnicu', 'Pitesti', 'Bucharest'] 418
print(len(expanded))     # 12
print(expanded[:6])      # ['Arad', 'Zerind', 'Timisoara', 'Sibiu', 'Oradea', 'Rimnicu']

	BFS	DFS	UCS
Complete?	Yes (finite `b`)	No in infinite spaces or with loops (tree search); yes for finite graph search	Yes if every step cost ≥ `ε > 0`
Optimal?	Only if all step costs are equal	No	Yes
Time	`O(bᵈ)`	`O(bᵐ)`	`O(b^(1 + ⌊C*/ε⌋))`
Space	`O(bᵈ)` — keeps the whole frontier	`O(bm)` — only the current path + siblings	`O(b^(1 + ⌊C*/ε⌋))`

When is BFS optimal?

Why must UCS test the goal on expansion rather than generation?

Is Dijkstra's algorithm the same as UCS?