Indian Computing Olympiad

Advanced graph algorithms

Prims's algorithm

The other approach is to grow the tree systematically, rather than constructing a forest and combining components.

Start with a edge of minimum weight. This edge should be in the final tree and will be connected to the rest of the tree at (at least) one of its end-points. Choose the smallest outgoing edge from either end point.

At any stage, we have a set of vertices S that are already connected as a tree by a set of edges T.

To add a new vertex to S, pick the smallest edge (u,v) from u in S to v outside S. Add v to S and (u,v) to T.

Example:

                   b       40      c
                    o-------------o
                 2 / \            |
                  /   \           |
               a o--   \17        | 18
                 |  \10 \         |
              15 |   ----\ d  65  |
               e o--------o ------o h
                  \  40    \     /
                   \        \3  /25
                 20 \        \ /
                      o-------o
                      f  13   g
      

Edge (a,b) of length 2 is minimum overall edge, so set

       S = {a,b}
       T = {(a,b)}
      

Now we have to consider all edges out of S. (In the picture, edges in T are labelled %, vertices in S are labelled *).

                     b       40      c
                      *-------------o
                   8 % \
                    %   \
                 a *--   \17
                   |  \10 \
                15 |   ----\ d
                 e o        o
      

Smallest outgoing edge from S is (a,d), so

       S = S U {d} = {a,b,d}
       T = T U {(a,d)} = {(a,b),(a,d)}
      

                     b       40      c
                      *-------------o
                   8 % \
                    %   \
                 a *%% --\17
                   |  % 10\
                15 |   %%%%\ d  65
                 e o--------* ------o h
                       40    \
                              \3
                                o
                                g
      

…

Does it matter that we start with the shortest edge?

It does not matter. Why?

Implementation:

The code is a variant of Dijkstra's algorithm. At each stage, when you burn a vertex u, you update the expected burn time of each unburnt vertex v as the minimum of

• current shortest edge from burnt vertices to v
• cost of the edge (u,v)

The difference from Dijkstra's algorithm is that we don't incorporate the burn time of u in the cost.

Again, we can use a heap to calculate the minimum unburnt vertex. In the heap, we would keep the minimum cost edge from the burnt vertices to each unburnt vertex. (We only need to keep the smallest currently known edge to each unburnt vertex.)

The complexity analysis is similar to Dijkstra.

Video lecture on Prim's algorithm, NPTEL online course on Design and Analysis of Algorithms (Lecture slides)