CSE201, Winter 2025, Lec 3: The BFS loop invariant
C. Seshadhri · 90:01
This lecture proves the BFS theorem from a loop invariant (the invariant itself is homework): after BFS finishes, a vertex is visited iff it is reachable from the source \(S\); its predecessor is null iff it is \(S\)...