Comment on page

# 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