Indian Computing Olympiad

Training Material

Basic Graph Algorithms

Breadth-first search

Here is the code for breadth-first search for a general graph, starting from some vertex v. 

       BFS(v){

         mark(v);
         add v at the end of the Queue;  /* Queue was empty */

         while the Queue is not empty{
           remove the vertex w at the head of the Queue;
           for each unmarked neighbour u of w{
             mark(u);
             add u to the end of the Queue;
           }
         }
       }

For instance, BFS(1) on the following graphs generates the queue

1, 2, 3, 4, 5, 8, 6, 7 

          1
         / \
        2---3
        |                   
        4---8
        |   |
        5   7
         \ /
          6

The order which the vertices are visited by BFS gives the shortest path. How do we recover the length of the path? We can record the length of the shortest path to each vertex w when we add it to the queue. This is just one more than the length of the shortest path to its parent. 

       BFS(v){

         mark(v);
         length(v) = 1;
         add v at the end of the Queue;  /* Queue was empty */

         while the Queue is not empty{
           remove the vertex w at the head of the Queue;
           for each unmarked neighbour u of w{
             mark(u);
             length(u) = length(w)+1;
             add u to the end of the Queue;
           }
         }
       }

To actually recover the path, once again, we can also record parent(u)=w when we explore w and add u to the queue. 

       BFS(v){

         mark(v);
         length(v) = 1;
         add v at the end of the Queue;  /* Queue was empty */

         while the Queue is not empty{
           remove the vertex w at the head of the Queue;
           for each unmarked neighbour u of w{
             mark(u);
             length(u) = length(w)+1;
             parent(u) = w;
             add u to the end of the Queue;
           }
         }
       }

BFS tree

When we explore a graph using breadth first tree, we can represent the visited nodes as a tree, called the BFS tree.

Consider the following graph. 

                b
               / \
              /   \
             a     c
              \   /|\
               \ / | \
                d--+--e
               / \ |  |
              /   \|  |
             i-----j  |
                   |  f
                   | / \
                   |/   \
                   g-----h

Suppose we start BFS at b

  • From b, we visit a,c (level 1) — queue is {a,c}
  • From a, we visit d (level 2) — queue is {c,d}
  • From c, we visit j,e (level 2) — queue is {d,j,e}
  • From d, we visit i (level 3) — queue is {j,e,i}
  • From j, we visit g (level 3) — queue is {e,i,g}
  • From e, we visit f (level 3) — queue is {i,g,f}
  • From i, no unmarked neighbours — queue is {g,f}
  • From g, we visit h (level 4) — queue is {f,h}
  • From f, no unmarked neighbours — queue is {h}
  • From h, no unmarked neighbours — queue is {}
  • Empty queue, so we stop

If draw the vertices that we visit in BFS level by level, we get the following tree, called the BFS tree. 

               ---b ---
              /         \
             a            c
             |          /   \
             d        j       e
             |        |       |
             i        g       f
                      |
                      h

The edges in this tree come from the graph. There are some edges in the graph that do not appear in this tree. In this case, they are {(c,d), (d,e), (d,j), (f,g), (f,h)}. If we add these edges to this tree we get a picture like this. 

               --- b ---
              /          \
             a   ......... c
             | .         /   \
             d ....... j       e...
             | .       |       |   .
             i  .      g ..... f   .
                 .     |       .   .
                  .    h .......   .
                   .               .
                    ................

In this figure, we refer to the original edges (---) as tree edges and the new edges (..., not used in the tree) as cross edges.

Note that cross edges either connect at same level or adjacent levels. Cross edges cannot cross two levels. (Why?)

Video material

Video lecture on Breadth first search, NPTEL online course on Design and Analysis of Algorithms (Lecture slides)



Basic topics

Advanced topics