# Editing Breadth-first search

**Warning:** You are not logged in. Your IP address will be publicly visible if you make any edits. If you **log in** or **create an account**, your edits will be attributed to your username, along with other benefits.

The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.

Latest revision | Your text | ||

Line 1: | Line 1: | ||

'''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 [[Depth-first search|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. | '''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 [[Depth-first search|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"; for this particular graph, for example, visiting all the vertices in numerical order is a possible ordering for a BFS starting from vertex 1. | 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"; for this particular graph, for example, visiting all the vertices in numerical order is a possible ordering for a BFS starting from vertex 1. | ||

− | + | =Implementation= | |

− | + | ||

<pre> | <pre> | ||

input G | input G | ||

Line 22: | Line 21: | ||

</pre> | </pre> | ||

''F'' has been replaced by a [[queue]], ''Q'', because a queue satisfies exactly the necessary property for BFS: the most recently added item is the last to be removed. | ''F'' has been replaced by a [[queue]], ''Q'', because a queue satisfies exactly the necessary property for BFS: the most recently added item is the last to be removed. | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

[[Category:Pages needing diagrams]] | [[Category:Pages needing diagrams]] | ||

[[Category:Algorithms]] | [[Category:Algorithms]] |