If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

The breadth-first search algorithm

Breadth-first search assigns two values to each vertex v:
  • A distance, giving the minimum number of edges in any path from the source vertex to vertex v.
  • The predecessor vertex of v along some shortest path from the source vertex. The source vertex's predecessor is some special value, such as null, indicating that it has no predecessor.
If there is no path from the source vertex to vertex v, then v's distance is infinite and its predecessor has the same special value as the source's predecessor.
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 k from the source before visiting any vertex at distance k+1.
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() returns true if the queue currently contains no objects, and false if 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 k followed by vertices with distance k+1. That's how we ensure that we visit all vertices at distance k before visiting any vertices at distance k+1.
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?

  • aqualine ultimate style avatar for user wchargin
    So is Dijkstra's algorithm essentially just BFS but with a priority queue instead of a normal queue? (And adding weights instead of just adding 1.)
    (5 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)
  • blobby green style avatar for user Ryan
    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);
    }
    }
    }
    (5 votes)
    Default Khan Academy avatar avatar for user
  • male robot hal style avatar for user Alexandros
    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)
    Default Khan Academy avatar avatar for user
  • male robot johnny style avatar for user Kevin Chow
    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)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)
  • blobby green style avatar for user yudonghan
    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)
    Default Khan Academy avatar avatar for user
  • piceratops sapling style avatar for user Peter Liu
    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)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      The two issues are:
      1) isEmpty is a method not a property ( try isEmpty() 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)
  • winston baby style avatar for user redmermaid2006
    Why does 4 visit 1 instead of 5? Why doesn't 3 visit 7? Other than that, this algorithm makes sense.
    (2 votes)
    Default Khan Academy avatar avatar for user
  • leaf green style avatar for user nnzxz1230
    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)
    Default Khan Academy avatar avatar for user
    • starky ultimate style avatar for user jdsutton
      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)
  • purple pi purple style avatar for user LeAnn Weaver
    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)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user mickey171904
    What does var...=graph [ ][ ] mean?
    Can you explain the condition "for"?
    (1 vote)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)