Prim's Algorithm

Concept

Prim's algorithm finds the minimum spanning tree for a undirected connected weighted graph.

Minimum spanning tree (MST) of a undirected connected weighted graph connects all the vertices together with minimal total weight for all its edges.

This is useful in communication networks where you need to connect a set of nodes with minimal total length. 

From visited vertices,search for a vertex with min edge cost.Put this vertex in visited set.Repeat until all vertices are visited.

Start from any arbitrary vertex(1 here).Put it in visited vertices set.V = {1}

Search for vertex with min edge cost from 1 (vertex=3,edge 1--3).Put 3 in V = {1,3}

Search for vertex with min edge cost from 1,3 (vertex=6,edge 3--6). V = {1,3,6}

Search for vertex with min edge cost from 1,3,6 (vertex=4,edge 3--4).V = {1,3,6,4}

Search for vertex with min edge cost from 1,3,6,4 (vertex=5,edge 6--5).V = {1,3,6,4,5}

Search for vertex with min edge cost from 1,3,6,4,5(vertex=2,edge 5--2).V = {1,3,6,4,5,2}

STOP

Terms

Cost matrix : Associate each edge with cost.Suppose there is an edge between i--j then 

cost_mat[i][j] = cost_mat[j][i] = cost of edge(i--j)

Suppose there is no edge between i--j then

cost_mat[i][j] = cost_mat[j][i] =  ∞ 

from[] : Cost is calculated from which vertex.

from[3] = 1 means cost is calculated from vertex 1 to 3 i.e for edge 1--3.

cost[] : Cost from a particular vertex.

cost[3] = 2 & from[3] = 1 means cost calculated from vertex 1 to 3 

i.e for edge 1--3 = 2

Algorithm

1. Make an arbitrary vertex(v) as current.
   Mark current vertex as visited.(vis[v]=1)
   Update cost[i](cost of ith vertex from current)
              from[i] (current vertex as cost is calc from there)
              initialize vis[i]=0 where v≠i

2. Taking only unvisited vertices into account,
      Find min cost in cost[].Make that vertex as current and mark it visited.

      For all vertices,check if lesser cost edge exists between the current vertex----i
      If it exists then
                      Update cost[i](cost from current vertex--i)
                      Update from[i](current vertex)

      Repeat from 2 until all vertices are visited.

Code

void prim()
{
    int curr,prev,total_min_cost = 0,i,j,min_cost;

    curr = 1;
    vis[1] = 1;

    for(j=2;j<=n;j++)                               //update cost[],from[] and vis[]
    {
        cost[j] = cost_mat[1][j];
        from[j]=1;
        vis[j]=0;
    }

    for(i=1;i<n;i++)
    {
        min_cost = 999;

        for(j=2;j<=n;j++)                           //min cost in cost[]
        {
            if(vis[j]==0 && cost[j]<min_cost)
            {
                min_cost = cost[j];
                curr = j;
            }
        }   
        prev= from[curr];

        //edge in MST from prev-->curr
        printf("\nEdge %d---%d  Cost = %d",prev,curr,min_cost);         
        total_min_cost = total_min_cost + min_cost;

        vis[curr]=1;

        for(j=2;j<=n;j++)                           //update cost[],from[]
        {
            if(vis[j]==0 && cost_mat[curr][j] < cost[j])
            {
                from[j] = curr;
                cost[j] = cost_mat[curr][j];
            }
        }
    }
    printf("\n\nMin cost = %d",total_min_cost);
}

Code Tracing

   Vertices      1     2     3     4     5     6

    vis[]        1     0     0     0     0     0
   cost[]        -     6     2     5     ∞     ∞
   from[]              1     1     1     1     1                     curr = 1

    vis[]        1     0     1     0     0     0
   cost[]        -     6     2     2     6     1
   from[]              1     1     3     3     3                     curr = 3

    vis[]        1     0     1     0     0     1
   cost[]        -     6     2     2     3     ∞
   from[]              1     1     3     6     1                     curr = 6

    vis[]        1     0     1     1     0     1
   cost[]        -     6     2     2     3     ∞
   from[]              1     1     3     6     1                     curr = 4

    vis[]        1     0     1     1     1     1
   cost[]        -     4     2     2     3     ∞
   from[]              5     1     3     6     1                     curr = 5

    vis[]        1     1     1     1     1     1
   cost[]        -     4     2     2     3     ∞
   from[]              5     1     3     6     1                     curr = 2

O/P