Breadth-first search
Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the root (or an arbitrary node in the case of a graph) and explores the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.
Algorithm[edit | edit source]
The BFS algorithm works as follows:
- Start by placing the root node in a queue.
- Mark the root node as visited.
- While the queue is not empty:
- Remove the node at the front of the queue.
- For each of the node's neighbors:
- If the neighbor has not been visited:
- Mark it as visited.
- Add it to the queue.
- If the neighbor has not been visited:
Properties[edit | edit source]
- Completeness: BFS is complete, meaning it will find a solution if one exists.
- Optimality: BFS is optimal if all edges have the same cost.
- Time complexity: The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges.
- Space complexity: The space complexity of BFS is O(V), where V is the number of vertices.
Applications[edit | edit source]
BFS is used in various applications, including:
- Finding the shortest path in an unweighted graph.
- Web crawling.
- Social network analysis.
- Broadcasting in computer networks.
- Garbage collection in computer science.
Pseudocode[edit | edit source]
Here is a pseudocode representation of the BFS algorithm:
``` BFS(G, start_vertex):
create a queue Q enqueue start_vertex onto Q mark start_vertex as visited while Q is not empty: current_vertex = dequeue Q for each neighbor of current_vertex: if neighbor has not been visited: mark neighbor as visited enqueue neighbor onto Q
```
Related Algorithms[edit | edit source]
See Also[edit | edit source]
Related Pages[edit | edit source]
Navigation: Wellness - Encyclopedia - Health topics - Disease Index - Drugs - World Directory - Gray's Anatomy - Keto diet - Recipes
Search WikiMD
Ad.Tired of being Overweight? Try W8MD's physician weight loss program.
Semaglutide (Ozempic / Wegovy and Tirzepatide (Mounjaro / Zepbound) available.
Advertise on WikiMD
WikiMD is not a substitute for professional medical advice. See full disclaimer.
Credits:Most images are courtesy of Wikimedia commons, and templates Wikipedia, licensed under CC BY SA or similar.Contributors: Prab R. Tumpati, MD