Breadth First Search (BFS)
Breadth First Search (BFS), like Depth First Search (DFS), is a method of traversing a graph. BFS simply traverses in a different order, but otherwise is very similar to DFS.
The main difference is that BFS visits all children before any subgraphs. In a tree, we call this level order.
For the example tree above, a level order traversal would go in this order: D B F A C E G.
Let's see how we might implement BFS.
Some data structures we will need are:
- A graph to traverse.
- A queue Q to keep track of which nodes need to be processed next.
- A list of booleans marked to keep track of which nodes were already visited.
- (Optional) edgeTo and distTo to keep track of information that might be useful for other applications (like Dijkstra's Algorithm).
First, let's start with a vertex in the graph by marking it and adding it to the queue.
The next step is to remove A from the queue and add its children (B and C) to the queue. Also, we need to mark all of the children.
Next, we'll move onto the next item on the queue (B). We'll do the same thing that we did with A: remove B, mark all its children, and add its children to the queue. Since C is already marked, we do not add it to the queue again.
Now, we'll move on to the next item on the queue, C, and do the same thing. Again, we won't add C or A because they are both marked.
Finally, we'll visit the two remaining nodes in the queue, D and E. Since all of the nodes are marked now, there aren't any other nodes to visit.
Last modified 3yr ago