Difference between revisions of "Breadth-first search"
(Created page with ''''Breadth-first search''' (BFS) is the type of graph search that arises when the oldest vertex on the fringe is always the first to leave it. Though its uses are not as wide…') |
m (+cat:pages needing diagrams) |
||
| Line 5: | Line 5: | ||
=Implementation= | =Implementation= | ||
| + | |||
| + | |||
| + | [[Category:Pages needing diagrams]] | ||
Revision as of 03:54, 19 November 2009
Breadth-first search (BFS) is the type of graph search that arises when the oldest vertex on the fringe is always the first to leave it. Though its uses are not as widespread as those of DFS, its specific application to the problem of finding shortest paths in unweighted graphs provides an example of a model algorithm: an algorithm which solves one particular, precisely specified (yet important) problem, solves it well (in minimal time and space), and is easy to understand and to implement.
Principles
The name breadth-first search reflects the fact that BFS attempts to "spread out" from the source vertex as much as possible. After the source vertex is visited, all of its neighbours are added to the fringe. Since they have been added at this early stage, any future vertices added to the fringe will not be visited until after all of the source vertex's immediate neighbours. As each of these immediate neighbours is visited, its immediate neighbours are added too, but it is not until all the immediate neighbours of the source vertex have been visited that these newly added vertices are visited. Now we know that all of these newly added vertices of distance 2 from the source will be visited before any more distant vertices. So BFS visits all the vertices with distance 1 from the source, then all the vertices with distance 2 from the source, and so on; it appears to "radiate" out from the source vertex. As an example, consider the graph ({1,2,3,4,5,6,7},{(1,2),(1,3),(2,4),(2,5),(3,6),(3,7)}). Suppose the source vertex is 1. After it is visited, 2 and 3 are added to the fringe. If 2 is visited next, then 4 and 5 will be added to the fringe, but before either of these can be visited, it is 3's turn, since it was in the fringe earlier. So 3 is visited next, with 6 and 7 being added to the fringe. Now, however, 6 and 7 must wait for 4 and 5 to be visited, since they arrived in the fringe earlier. Evidently, BFS has a great tendency to "jump around", in this case, possibly visiting the vertices of the graph in increasing numerical order of label.
