En kısa yol: genişlemesine arama

Derinlemesine arama bir yol bulur ama en kısasını bulmaz. En kısa yol için sırayı değiştirirsin: önce başlangıcın bütün komşuları, sonra onların komşuları. Suya atılan taşın halkaları gibi dışarı yayılırsın; bir düğüme ilk vardığında oraya en az adımla varmışsındır. Buna genişlemesine arama (BFS) denir.

1from collections import deque
2queue = deque([(start, 0)])
3seen = {start}
4while queue:
5    node, steps = queue.popleft()
6    if node == goal:
7        return steps
8    for nxt in graph[node]:
9        if nxt not in seen:
10            seen.add(nxt)
11            queue.append((nxt, steps + 1))
12return -1

Bu, her adımın aynı "maliyette" olduğu durumlar için geçerlidir (ızgarada bir kare, labirentte bir hamle). Enerjin sınırlıysa ya da en yakın hedefi arıyorsan kuş uçuşu mesafe seni yanıltır: duvarın arkasındaki yakın hedef, uzaktaki açık hedeften daha pahalı olabilir. Mesafeyi BFS ile ölç.