Intuitively, Breadth-First Search (BFS) can find shortest distances from a source $latex s&s=4$ to any other reachable vertex. However, proving this intuition needs a bit hard work. After some searches, I found that there are two ideas to prove it. The two ideas both use induction to prove it. Both ideas require a bit long proof.
- The first idea is based on CLRS Page 597-600. The second reference below is talking about the same idea.
- The second idea is from a pdf file from NYU. (the third reference)
References:
- CLRS Page 597 – 600
- http://www.cs.toronto.edu/~krueger/cscB63h/lectures/BFS.pdf
- http://www.cs.nyu.edu/courses/fall03/G22.1170-001/bfs.pdf
Here I am showing my proof, a small variant of CLRS:
