BFS This is called the breadth-first search(BFS). ■Why it works? [Thm]If we find t in Step k,then d(s,t)=k. Or equivalently, [Thm]Ni(s)contains exactly those vertices with distance k from s. 14BFS ◼ This is called the breadth-first search (BFS). ◼ Why it works? ◼ [Thm] If we find 𝑡 in Step 𝑘, then 𝑑(𝑠,𝑡) = 𝑘. Or equivalently, ◼ [Thm] 𝑁𝑘(𝑠) contains exactly those vertices with distance 𝑘 from 𝑠. 14