BFS is an algorithm used to visit all the nodes in a graph or tree, visiting them by levels of distance from the origin node.
If you have a tree with this structure:
1 2 3 4 5 6 7 8 9 10
You would visit the nodes in this order (by levels):
You will visit each level of nodes, starting with the selected origin node. Each node that you visit will be marked as such and will know who was its parent (the node of the previous level from which we came).
This algorithm can be expressed iteratively in a very easy way.
It uses a queue to make sure a new level is not visited until the current level is visited completely.
BFS(root): root.visited = True Queue q = [root] while not q.empty(): x = q.dequeue() for neighbor in x.neighbors(): if not neighbor.visited: neighbor.visited = True neighbor.parent = x q.enqueue(neighbor)
|V| is the number of vertices (nodes) and |E| is the number of edges (connections).
Time: it will take the algorithm O(|V| + |E|) to visit all the nodes.
Space: it will use a space equivalent to O(|V|) due to the usage of a queue. It will also use O(|V|+|E|) if you use an adjacency list for the edges, or O(|V|2) if you use an adjacency matrix (when you know that you will have a maximum or fixed number of nodes).