Searching a single layer (Algorithm 2)·6 min
The greedy walk
0 / 1
SEARCH-LAYER(q, ep, ef, layer) is a best-first graph traversal — the heart of both insert and query. Start from entry point(s) ep. Keep v (visited set), C (min-heap of candidates), and W (max-heap holding the best ef found). Repeatedly pop the nearest candidate; if it is further than your furthest keeper, stop; otherwise expand its neighbors, pushing unvisited ones into C and W (evicting W's furthest when it overflows ef).
Algorithm 2, paraphrased
v <- {ep}; C <- {ep}; W <- {ep} // candidates and results seeded
while C not empty:
c <- extract-nearest(C) // min-heap pop
f <- furthest(W) // max-heap peek
if dist(c, q) > dist(f, q) and |W| >= ef:
break // STOP: best is locked in
for e in neighbors(c, layer):
if e in v: continue
v <- v ∪ {e}
if dist(e, q) < dist(f, q) or |W| < ef:
C <- C ∪ {e}; W <- W ∪ {e}
if |W| > ef: remove furthest(W)
return W
A 3-hop walk converging on q
q n0 -- n1 -- n2 -- n3 -- n4 -- n5
* |entry \______ closer ______/
hop 1: pop n0, expand -> n1 closer, push
hop 2: pop n1, expand -> n2,n3 closer, push
hop 3: pop n3, expand -> nothing beats W's worst -> STOP