English subtitles

← 03-16 Depth vs Breadth First Search

Get Embed Code
3 Languages

Showing Revision 2 created 10/24/2012 by Amara Bot.

  1. To get a handle on how to best find shortest paths in a graph,
  2. it's going to help to compare a little bit between the kinds of depth first search algorithms
  3. that we were looking at with the kinds of breadth first search algorithms
  4. that we're going to need to look at.
  5. So let's consider what the check_connection algorithm that we were just talking about does
  6. if it's given this graph, G, and we ask it to check the connection between i and n.
  7. The flow of control is when we do check_connection on i and n,
  8. checking to see whether i and n are connected in the graph,
  9. the way that it proceeds is it starts off at i
  10. then visits the neighbors of i in some order.
  11. Let's say it visits j first and then it asks, "Has j been visited so far? i has."
  12. "Has j been visited so far?" No.
  13. "Okay, well, let's go to j and do a mark_component from j."
  14. It's going to consider the neighbors of j in some order.
  15. Let's say it considers k first. "Has k been visited?" No.
  16. "All right. Let's go mark_component on k." And so on.
  17. So at some point, it may actually check one of the neighbors that it's already visited,
  18. but at this point, once it's kind of heading in this direction,
  19. it's going to continue to explore the graph this way,
  20. and it will eventually hit n.
  21. Essentially, the path that it followed to get to n is 1, 2, 3, 4, 5 links long,
  22. which is not very representative of the shortest path, which in this case is just the 1 link.
  23. So partly what's going on when you run this kind of algorithm
  24. is it's diving deep into the graph.
  25. It starts off at i and it just keeps digging itself deeper and deeper
  26. and deeper and deeper and deeper.
  27. And really what we'd like to do is kind of check in circles around i.
  28. We start at i and check the things that are close to i before the things that are far from i.
  29. And that's the essence of what breadth first search is going to do.