Breadth-first search - Revision history

Brian at 23:33, 11 March 2011

2011-03-11T23:33:09Z

Jargon: Added implementation, categorized

2009-12-23T17:32:02Z

Added implementation, categorized

Brian at 01:42, 19 December 2009

2009-12-19T01:42:11Z

Jargon: +cat:pages needing diagrams

2009-11-19T03:54:23Z

+cat:pages needing diagrams

Brian: 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…'

2009-11-18T05:17:22Z

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…'

New page

'''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", in this case, possibly visiting the vertices of the graph in increasing numerical order of label.

=Implementation=

@@ 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.
-=Principles=
+==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.
-=Implementation=
+==Implementation==
 <pre>
 input G
@@ Line 21: / Line 22: @@
 </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.
 [[Category:Pages needing diagrams]]
 [[Category:Algorithms]]

@@ Line 5: / Line 5: @@
 =Implementation=
+<pre>
 [[Category:Pages needing diagrams]]

← Older revision		Revision as of 03:54, 19 November 2009
Line 5:		Line 5:

	=Implementation=		=Implementation=
		+
		+
		+	[[Category:Pages needing diagrams]]