Prim Algorithm - Finding Minimum Spanning Tree - Graph - dyclassroom

In this tutorial we will learn to find Minimum Spanning Tree (MST) using Prim's algorithm.

Minimum Spanning Tree

A spanning tree of a graph is a tree that has all the vertices of the graph connected by some edges. A graph can have one or more number of spanning trees.

If the graph has N vertices then the spanning tree will have N-1 edges. A minimum spanning tree (MST) is a spanning tree that has the minimum weight than all other spanning trees of the graph.

Graph

Consider the following graph.

We will find MST for the above graph shown in the image.

Steps

Step 1: Remove all loops

Any edge that starts and ends at the same vertex is a loop.

Loops are marked in the image given below.

Step 2: Remove all parallel edges between two vertex except the one with least weight

In this graph, vertex A and C are connected by two parallel edges having weight 10 and 12 respectively. So, we will remove 12 and keep 10.

We are now ready to find the minimum spanning tree.

Step 3: Create table

As our graph has 4 vertices, so our table will have 4 rows and 4 columns.

Now, put 0 in cells having same row and column name.

Find the edges that directly connects two vertices and fill the table with the weight of the edge. If no direct edge exists then fill the cell with infinity.

Finding MST

Start from vertex A, find the smallest value in the A-row.

Note! We will not consider 0 as it will correspond to the same vertex.

5 is the smallest unmarked value in the A-row. So, we will mark the edge connecting vertex A and B and tick 5 in AB and BA cell.

As we connected vertex A and B in the previous step, so we will now find the smallest value in the A-row and B-row.

4 is the smallest unmarked value in the A-row and B-row. So, we will mark the edge connecting vertex B and C and tick 4 in BC and CB cell.

As vertex A-B and B-C were connected in the previous steps, so we will now find the smallest value in A-row, B-row and C-row.

5 is the smallest unmarked value in the A-row, B-row and C-row. So, we will mark the edge connecting vertex C and D and tick 5 in CD and DC cell.

Result

Following is the required Minimum Spanning Tree for the given graph.

Code

Note! In the given code we are representing Vertices using decimal numbers.
So,
vertex A is denoted by digit 0.
vertex B is denoted by digit 1.
vertex C is denoted by digit 2.
vertex D is denoted by digit 3.

/**
 * file: prim.c
 * author: yusuf shakeel
 * date: 2014-03-02
 *
 * description: find MST using prim's algorithm
 *
 * vertices are represented using numbers.
 * vertex A becomes 0
 * vertex B becomes 1
 * and so on...
 */

#include <stdio.h>
#include <stdlib.h>

/**
 * contant to represent infinity
 * it is assumed that edges of the graph will have weight less than this value
 */
#define INF 9999

/**
 * total number of vertices in the graph
 */
#define V 4

/**
 * this function will display the MST
 */
void displayMST(int graph[V][V], int markedCell[V][V]) {
  
  int r, c;

  for (r = 0; r < V-1; r++) {
    for (c = r+1; c < V; c++) {
      if(markedCell[r][c]) {
        printf("Edge: %d -- %d\tWeight: %d\n", r, c, graph[r][c]);
      }
    }
  }

}

/**
 * prim&aposs algorithm function
 */
void prim(int graph[V][V]) {

  //variables
  int i, r, c,
    solved = 0,
    count = 0,
    min,
    expectedR,
    expectedC;

  /**
   * this array holds the marked cells in the graph
   */
  int markedCell[V][V] = {{0}};

  /**
   * this array holds the marked vertices
   * 0 = unmarked
   * 1 = marked
   */
  int markedVertex[V] = {0};
  markedVertex[0] = 1;

  
  /**
   * find MST
   */
  while(!solved) {

    min = INF;
    count = 0;
    expectedR = -1;
    expectedC = -1;

    /**
     * find minimum weight from marked vertex
     *
     * note!
     * graph[][] is a square matrix
     * diagonal elements of the graph[][] are zeros
     * and elements on either sides are same
     * example: element graph[1][0] is same as graph[0][1]
     * so, we will check only one side of the diagonal
     */
    for (r = 0; r < V; r++) {

      if (markedVertex[r] == 1) {

        for (c = r; c < V; c++) {

          if (graph[r][c] != 0 && graph[r][c] < min && !markedCell[r][c]) {

            min = graph[r][c];
            expectedR = r;
            expectedC = c;

          }

        }

      }

    }

    /**
     * mark the newly found vertex for MST
     */
    if (expectedR != -1 && expectedC != -1) {
      markedCell[expectedR][expectedC] = 1;
      markedCell[expectedC][expectedR] = 1;
      markedVertex[expectedR] = 1;
      markedVertex[expectedC] = 1;
    }

    /**
     * check if the graph is solved
     */
    for (i = 0; i < V; i++) {
      if (markedVertex[i]) {
        count++;
      }
    }
    if (count == V) {
      solved = 1;
    }

  }

  displayMST(graph, markedCell);

}

/**
 * this is the main function
 */
int main(void) {

  /**
   * 2d array which holds the weight of the edges 
   *
   * note!
   * graph[][] is a square matrix
   * diagonal elements of the graph[][] are zeros
   * and elements on either sides are same
   * example: element graph[1][0] is same as graph[0][1]
   */  
  int graph[V][V] = {
    {0, 5, 10, INF},
    {5, 0, 4, 11},
    {10, 4, 0, 5},
    {INF, 11, 5, 0}
  };

  /**
   * find MST using prim
   */
  prim(graph);

  return 0;
}

Output

Edge: 0 -- 1  Weight: 5
Edge: 1 -- 2  Weight: 4
Edge: 2 -- 3  Weight: 5

More topics

Prim Algorithm - Finding Minimum Spanning Tree