TuongOnArrival1's blog

Need help with BFS
By TuongOnArrival1, history, 15 months ago, In English

Can anyone explain to me why the BFS algorithm finds the shortest distance from u to v ? i understand but i am unable toexplain it, i think i don't understand it enough.. :( ( my writing is bad sorry)

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Since the way BFS works is by going through levels (first the closest are visited (directly adjacent), then the second closest (neighbours of adjacent)), thats why BFS will always find the best distance. the distance of v will always be the level it is at from the starting vertex.

→ Reply
»
15 months ago, hide # |
← Rev. 3  
Vote: I like it +2 Vote: I do not like it

If we wish to find the shortest path from U to V in a tree:

We start BFS at U, effectively "hanging" the tree by U (in a tree you can re-designate any vertex as root).

By the nature of BFS, we first consider all verices that are adjacent to U (one edge away), then the ones that are adjacent to them (two edges away) and so on. In other words, traverse the tree "level by level".

We consider all vertices on a level before moving on to the next one. We also don't consider the same vertex twice.

Because of this, when we encounter a given vertex V on a level X, X must be the shortest distance to it. If it weren't, we would've encountered it earlier.

Keep in mind that this only works when the edges are not weighted (or all have the same weight).

→ Reply