Breadth-first search
In computer science, breadth-first search (BFS) is a method used for traversing a graph. It starts at any item you want to use as a starting position in a graph, and explores all of the neighbor items at the present depth before to moving on to the items at the next depth level. A breadth-first search done on a tree (data structure) is called a level-order traversal.
Implementation
<syntaxhighlight lang="java"> void breadthFirstSearch(Item root) {
Queue q = new Queue();
root.found = true;
q.enqueue(item);
while (!q.isEmpty()) {
Item v = q.dequeue();
for (Item neighbor : v.neighbors()) {
if (!neighbor.found) {
neighbor.found = true;
q.enqueue(neighbor);
}
}
}
} </syntaxhighlight>
Usage
Though they have usage in a variety of disciplines, breadth first search algorithms are most often associated with finding the shortest distance between two points, such as on a map.
Breadth-first Search Media
BFS on Maze-solving algorithm
- Error creating thumbnail: About to transcode 1 SVG file(s)
Converting Tic-tac-toe-game-tree.svg to /var/www/html/w/images/temp/transform_d19d44a92f17.png ... org.apache.batik.transcoder.TranscoderException: null Enclosed Exception: file:/var/www/html/w/images/temp/svg_ee94f51f3e55615eab05fb55/Tic-tac-toe-game-tree.svg:-1 Cannot find the referenced element: "#use7837" specified on the element <use> - may be a problem of 'id' at org.apache.batik.transcoder.SVGAbstractTranscoder.transcode(SVGAbstractTranscoder.java:228) at org.apache.batik.transcoder.image.ImageTranscoder.transcode(ImageTranscoder.java:92) at org.apache.batik.transcoder.XMLAbstractTranscoder.transcode(XMLAbstractTranscoder.java:142) at org.apache.batik.transcoder.SVGAbstractTranscoder.transcode(SVGAbstractTranscoder.java:158) at org.apache.batik.apps.rasterizer.SVGConverter.transcode(SVGConverter.java:1008) at org.apache.batik.apps.rasterizer.SVGConverter.execute(SVGConverter.java:719) at org.apache.batik.apps.rasterizer.Main.execute(Main.java:956) at org.apache.batik.apps.rasterizer.Main.main(Main.java:1009) Caused by: org.apache.batik.bridge.BridgeException: file:/var/www/html/w/images/temp/svg_ee94f51f3e55615eab05fb55/Tic-tac-toe-game-tree.svg:-1 Cannot find the referenced element: "#use7837" specified on the element <use> - may be a problem of 'id' at org.apache.batik.bridge.BridgeContext.getReferencedNode(BridgeContext.java:762) at org.apache.batik.bridge.BridgeContext.getReferencedElement(BridgeContext.java:804) at org.apache.batik.bridge.SVGUseElementBridge.buildCompositeGraphicsNode(SVGUseElementBridge.java:124) at org.apache.batik.bridge.SVGUseElementBridge.createGraphicsNode(SVGUseElementBridge.java:98) at org.apache.batik.bridge.GVTBuilder.buildGraphicsNode(GVTBuilder.java:213) at org.apache.batik.bridge.GVTBuilder.buildComposite(GVTBuilder.java:171) at org.apache.batik.bridge.GVTBuilder.build(GVTBuilder.java:82) at org.apache.batik.transcoder.SVGAbstractTranscoder.transcode(SVGAbstractTranscoder.java:210) ... 7 more ... error (SVGConverter.error.while.rasterizing.file)
Top part of Tic-tac-toe game tree
An example map of Southern Germany with some connections between cities
The breadth-first tree obtained when running BFS on the given map and starting in Frankfurt
