Main content
The breadth-first search algorithm
Breadth-first search assigns two values to each vertex
- A distance, giving the minimum number of edges in any path from the source vertex to vertex
- The predecessor vertex of
null, indicating that it has no predecessor.
If there is no path from the source vertex to vertex
For example, here's an undirected graph with eight vertices, numbered 0 to 7, with vertex numbers appearing above or below the vertices. Inside each vertex are two numbers: its distance from the source, which is vertex 3, followed by its predecessor on a shortest path from vertex 3. A dash indicates
null:In BFS, we initially set the distance and predecessor of each vertex to the special value (
null). We start the search at the source and assign it a distance of 0. Then we visit all the neighbors of the source and give each neighbor a distance of 1 and set its predecessor to be the source. Then we visit all the neighbors of the vertices whose distance is 1 and that have not been visited before, and we give each of these vertices a distance of 2 and set its predecessor to be vertex from which we visited it. We keep going until all vertices reachable from the source vertex have been visited, always visiting all vertices at distance Given the example above, here are the steps plus a visualization to play through each step:
- Start by visiting vertex 3, the source, setting its distance to 0.
- Then visit vertices 2 and 6, setting their distance to 1 and their predecessor to vertex 3.
- Start visiting from vertices at distance 1 from the source, beginning with vertex 2. From vertex 2, visit vertices 4 and 5, setting their distance to 2 and their predecessor to vertex 2. Don't visit vertex 3, because it has already been visited.
- From vertex 6, don't visit vertex 5, because it was just visited from vertex 2, and don't visit vertex 3, either.
- Now start visiting from vertices at distance 2 from the source. Start by visiting from vertex 4. Vertex 2 has already been visited. Visit vertex 1, setting its distance to 3 and its predecessor to vertex 4.
- From vertex 5, don't visit any of its neighbors, because they have all been visited.
- Now start visiting from vertices at distance 3 from the source. The only such vertex is vertex 1. Its neighbors, vertices 4 and 5, have already been visited. But vertex 0 has not. Visit vertex 0, setting its distance to 4 and its predecessor to vertex 1.
- Now start visiting from vertices at distance 4 from the source. That's just vertex 0, and its neighbor, vertex 1, has already been visited. We're done!
Notice that because there is no path from vertex 3 to vertex 7, the search never visits vertex 7. Its distance and predecessor remain unchanged from their initial values of
null.A couple of questions come up. One is how to determine whether a vertex has been visited already. That's easy: a vertex's distance is
null until it has been visited, at which time it gets a numeric value for its distance. Therefore, when we examine the neighbors of a vertex, we visit only the neighbors whose distance is currently null.The other question is how to keep track of which vertices have already been visited but have not yet been visited from. We use a queue, which is a data structure that allows us to insert and remove items, where the item removed is always the one that has been in the queue the longest. We call this behavior first in, first out. A queue has three operations:
enqueue(obj)inserts an object into the queue.dequeue()removes from the queue the object that has been in it the longest, returning this object.isEmpty()returnstrueif the queue currently contains no objects, andfalseif the queue contains at least one object.
Whenever we first visit any vertex, we enqueue it. At the start, we enqueue the source vertex because that's always the first vertex we visit. To decide which vertex to visit next, we choose the vertex that has been in the queue the longest and remove it from the queue—in other words, we use the vertex that's returned from
dequeue(). Given our example graph, here's what the queue looks like for each step, plus the previous visualization shown with the queue state:- Initially, the queue contains just vertex 3 with distance 0.
- Dequeue vertex 3, and enqueue vertices 2 and 6, both with distance 1. The queue now contains vertex 2 with distance 1 and vertex 6 with distance 1.
- Dequeue vertex 2, and enqueue vertices 4 and 5, both with distance 2. The queue now contains vertex 6 with distance 1, vertex 4 with distance 2, and vertex 5 with distance 2.
- Dequeue vertex 6, and don't enqueue any vertices. The queue now contains vertex 4 with distance 2 and vertex 5 with distance 2.
- Dequeue vertex 4, and enqueue vertex 1 with distance 3. The queue now contains vertex 5 with distance 2 and vertex 1 with distance 3.
- Dequeue vertex 5, and don't enqueue any vertices. The queue now contains just vertex 1 with distance 3.
- Dequeue vertex 1, and enqueue vertex 0 with distance 4. The queue now contains just vertex 0 with distance 4.
- Dequeue vertex 0, and don't enqueue any vertices. The queue is now empty. Because the queue is empty, breadth-first search terminates.
Notice that at each moment, the queue either contains vertices all with the same distance, or it contains vertices with distance
This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.
Want to join the conversation?
So is Dijkstra's algorithm essentially just BFS but with a priority queue instead of a normal queue? (And adding weights instead of just adding1.)(5 votes)
I would suggest that BFS and Dijkstra's algorithm are similar in two respects:
-they both typically use a queue (although they use very different types of queues)
-they both keep track of nodes they have already visited
I believe the implementation of BFS shown in the article above might give you the impression that they are very similar, but there are different implementations of BFS.
BFS can be implemented without keeping track of distance from the source, or keeping track of predecessors.
A sketch of a very common BFS implementation is as follows:Put the starting node on a queue and marked it as visited
While the queue is not empty:
pop off the node at the head of the queue
If it is the node we are searching for Then exit and return the node
For all of the unvisited neighbors:
mark the neighbour as visited
put the neighbour in the queue
If we get here, the node is not reachable from the starting node, BFS failed
Note: distance and predecessors are not used in this implementation
Hope this makes sense(13 votes)
I'm stuck on the next challenge. I think I discovered how to access the neighbors of a vertex and change their "distance" and "predecessor" properties, but I'm not sure I understand how to implement them in code.while (!queue.isEmpty()) {
var u = queue.dequeue();
for (i = 0; i < graph[u].length; i++) {
var v = graph[u][i];
if (bfsInfo[i].distance === null) {
bfsInfo[i].distance = bfsInfo[u].distance + 1;
bfsInfo[i].predecessor = u;
queue.enqueue(v);
}
}
}(4 votes)- The problem is this:
bfsInfo[i]
Ask yourself the following:
Which vertex do I want info on ?
What vertex wouldbfsInfo[i]return info about ?
Is that the same vertex as the one I want info about ?(7 votes)
- I am stuck on the next challenge. I do not understand how i can access the neighbours of a vertix. What arguments should I use in the for loop?(5 votes)
- Here's a hint on how to find the neighbors of a vertex.
-you will want to usegraph
-graphis one of parameters for the function.graphis a Graph - represented as adjacency lists.
-you may want to review adjacency lists at: https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs(7 votes)
I'm confused as to dequeueing an element. If it is in the while loop, does that not mean at the beginning, you have dequeued the only element which is the source element? This immediately terminates the loop. What am I not seeing?(2 votes)- You only terminate the loop if at the start of the loop there is no elements on the queue.
On the first loop the queue has the source element.
When you dequeue it, the queue is empty, but we are still in the middle of the loop.
Then we add the neighbours of the source to the queue. The queue isn't empty anymore.
Then we start the next loop (unless source had 0 neighbours the queue is not empty).(9 votes)
while (!queue.isEmpty()) {
var u = queue.dequeue();
for (var i = 0; i < graph[u].length; i ++ ) {
var v = graph[u][i];
if (bfsInfo[v].distance === null) {
bfsInfo[v].distance = bfsInfo[u].distance + 1;
bfsInfo[v].predecessor = u;
queue.enqueue(v);
}
}
}(4 votes)
I am having issues with my code in the next challenge. I would really appreciate it if someone could tell me where I made a mistake. Thanks!
[Edited to show only relevant code]while(!queue.isEmpty)
{
...
if (bfsInfo[v].predecessor === null)
{
}
...
}(2 votes)- The two issues are:
1)isEmptyis a method not a property ( tryisEmpty()instead )
2) The predecessor of the starting node is set to null when you start, and you don't want to visit the starting node (you have already visited it, because that's where you came from). Right now, you will assign the start a non-zero distance, which doesn't make sense.
Would the distance property work better ? Note that the starting node is given a non-null distance before starting the while loop.(5 votes)
Why does 4 visit 1 instead of 5? Why doesn't 3 visit 7? Other than that, this algorithm makes sense.(2 votes)
In the next challenge, I wrote that if the predecessor is null, then we enqueue it, assign a distance and assign a predecessor to it. However I ran into a problem that since the predecessor of the source 3 is null, when I dequeue 2, the algorithm runs back to 3 and assigns a distance of 2 and a predecessor of 2 to it. I know this could be solved easily by adding some extra codes, but I couldn't get the form Hopper wanted. How could I solve this problem?(2 votes)
Hmm, it sounds like you are assigning the new node as the predecessor of the old one. It should be the other way around. Look over your code carefully and think about what it is doing. We can't help you any more without seeing your code.(1 vote)
I am stuck on this challenge (next page). Why can't I ask for help? It is very frustrating when there are not more hints on the lines like this: ....; I am able to assign the bfsInfo for the vertices of 2 and 6, then I don't know how to get the last part of the code where there are 3 statements with no hints as what to do on these 3 lines.(1 vote)
When (and if) you start programming on your own, there will be no hints at all. Debugging will be an essential part of your work. Therefore having limited hints is a good preparation for the future.(2 votes)
- What does var...=graph [ ][ ] mean?
Can you explain the condition "for"?(1 vote)- The ... in the hint code are blanks that you are supposed to fill in based on your understanding of the pseudocode.
I've put some more hints in comments here:while (!queue.isEmpty()) {
var ... = queue.dequeue();
//queue.dequeue returns a vertex represented
//as an adjacency list
//let's do something with that vertex we just got here
//for loops are usually what we use to loop through lists
for ( ... ; ... ; ... ) {
var ... = graph[ ... ][ ... ];
// graph[ ... ] returns a vertex represented as an adjacency list
// graph[ ... ][ ... ] returns the index of a vertex
//let's do something with the index we got here
//maybe the paragraph in the instructions that starts with:
//"For each vertex v," will give a hint
if (bfsInfo[ ... ]. ... === ... ) {
... ;
... ;
... ;
}
}
}(2 votes)
