This blog is under construction

Friday 31 May 2013

C Program To Find Minimum Spanning Tree Using Prim's Algorithm

Prim's algorithm is a greedy algorithm which is used to find the minimum spanning tree of the connected graph.

What is minimum spanning tree?
Minimum spanning tree is a connected sub graph which includes all vertices in the graph together without any cycles at minimum cost.

Input Graph:
                                 1                              6
                   +---------------------- V1 ----------------------+
                   |                                                           |
                   |            7                          3                  |
                  V2 --------------------+  +-----------------------V3
                   |                          |  |                            |
               2  |                          |  |                            |  4  
                   V4                        |  |                           V5
                   |                          |  |                            |
                   |                          |  |                            |
                   +---------------------- V6  ----------------------+
                                5                              8

Step 1:  Select the start vertex V1.
                                 1                              6
                   +---------------------- V1 ----------------------+
                   |                                                           |
                   |            7                          3                  |
                  V2 --------------------+  +-----------------------V3
                   |                          |  |                            |
               2  |                          |  |                            |  4  
                   V4                        |  |                           V5
                   |                          |  |                            |
                   |                          |  |                            |
                   +---------------------- V6  ----------------------+
                                5                              8

Step 2:  Find the unvisited edges connected to V1 and select the edge with minimum cost. Edge V1-V2 is selected since it has the minimum cost.

                                 1                              6
                   +---------------------- V1 ----------------------+
                   |                                                           |
                   |            7                          3                  |
                  V2 --------------------+  +-----------------------V3
                   |                          |  |                            |
               2  |                          |  |                            |  4  
                   V4                        |  |                           V5
                   |                          |  |                            |
                   |                          |  |                            |
                   +---------------------- V6  ----------------------+
                                5                              8
Step 3:  Find the unvisited edges connected to V2 and select the edge with minimum cost.  Edge V2-V4 is selected since it has the minimum cost.

                                 1                              6
                   +---------------------- V1 ----------------------+
                   |                                                           |
                   |            7                          3                  |
                  V2 --------------------+  +-----------------------V3
                   |                          |  |                            |
               2  |                          |  |                            |  4  
                   V4                        |  |                           V5
                   |                          |  |                            |
                   |                          |  |                            |
                   +---------------------- V6  ----------------------+
                                5                              8

Step 4:  Find the unvisited edges connected to V4 and select the edge with minimum cost.  Edge V4-V6 is selected since it has the minimum cost.

                                 1                              6
                   +---------------------- V1 ----------------------+
                   |                                                           |
                   |            7                          3                  |
                  V2 --------------------+  +-----------------------V3
                   |                          |  |                            |
               2  |                          |  |                            |  4  
                   V4                        |  |                           V5
                   |                          |  |                            |
                   |                          |  |                            |
                   +---------------------- V6  ----------------------+
                                5                              8

Step 5:  Find the unvisited edges connected to V6 and select the edge with minimum cost.  Edge V6-V3 is selected since it has the minimum cost. 

                                 1                              6
                   +---------------------- V1 ----------------------+
                   |                                                           |
                   |            7                          3                  |
                  V2 --------------------+  +-----------------------V3
                   |                          |  |                            |
               2  |                          |  |                            |  4  
                   V4                        |  |                           V5
                   |                          |  |                            |
                   |                          |  |                            |
                   +---------------------- V6  ----------------------+
                                5                              8

Step 6:  Find the unvisited edges connected to V3 and select the edge with minimum cost.  Edge V3-V5 is selected since it has the minimum cost.

                                 1                              6
                   +---------------------- V1 ----------------------+
                   |                                                           |
                   |            7                          3                  |
                  V2 --------------------+  +-----------------------V3
                   |                          |  |                            |
               2  |                          |  |                            |  4  
                   V4                        |  |                           V5
                   |                          |  |                            |
                   |                          |  |                            |
                   +---------------------- V6  ----------------------+
                                5                              8

Resultant Minimum Spanning Tree:

                                 1                            
                   +---------------------- V1
                   |                                                           
                   |                                        3                  
                  V2                             +-----------------------V3
                   |                             |                             |
               2  |                             |                             |  4  
                   V4                           |                            V5
                   |                             |                            
                   |                             |                            
                   +---------------------- V6 
                                5                             

Cost of the given Minimum Spanning Tree is 15.


Example Program To Implement Minimum Spanning Tree Using Prim's Algorithm:



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

  #define MAXVERTICES 1000
  #define INFINITY 99999

  struct vertex {
        int visited, predecessor;
        int dist;
  };

  int treeEdge[MAXVERTICES][2], mstCost;
  int graphEdge[MAXVERTICES][MAXVERTICES], nodeCount;
  struct vertex node[MAXVERTICES];

  /* construct the input graph */
  void buildGraph() {
        int i = 1, source, dest, weight;
        printf("Enter the no of vertices:");
        scanf("%d", &nodeCount);
        while (i <= (nodeCount * (nodeCount - 1) / 2)) {
                printf("Edge(x to y)/(x<->x to exit):");
                scanf("%d%d", &source, &dest);
                if (source == dest)
                        break;
                if (source > nodeCount || dest > nodeCount ||
                                source <= 0 || dest <= 0) {
                        printf("Not a valid edge!!\n");
                        continue;
                } else {
                        printf("Weight for the edge %d to %d:", source, dest);
                        scanf("%d", &weight);

                        /* update weight of the edge */
                        graphEdge[source][dest] = weight;
                        graphEdge[dest][source] = weight;
                }
                i++;
        }
        if (i < nodeCount - 1) {
                printf("Unable to build Minimum Spanning Tree\n");
                exit(0);
        }
        return;
  }

  /* all vertices are visited or not */
  int allVisited() {
        int i;
        for (i = 1; i <= nodeCount; i++)
                if (node[i].visited == 0)
                        return 0;
        return 1;
  }

  /* construct minimum spanning tree */
  int buildTree() {
        int i = 1, currentNode, count = 0, mindist;
        while (i <= nodeCount) {
                node[i].visited = 0;
                node[i].predecessor = 0;
                node[i].dist = INFINITY;
                i++;
        }

        node[1].visited = 1;
        node[1].dist = 0;

        currentNode = 1;
        while (allVisited() == 0) {
                for (i = 1; i <= nodeCount; i++) {

                        /* Find the adjacent vertices and update the edge lenght */
                        if(graphEdge[currentNode][i] > 0 && node[i].visited == 0) {
                                if (graphEdge[currentNode][i] < node[i].dist) {
                                        node[i].predecessor = currentNode;
                                        node[i].dist = graphEdge[currentNode][i];
                                }
                        }
                }

                mindist = INFINITY;
                /* find the edge with minimum legth */
                for (i = 1; i <= nodeCount; i++) {
                        if (node[i].dist < mindist && node[i].visited == 0) {
                                mindist = node[i].dist;
                                currentNode = i;
                        }
                }
                /* Mark the vertex as visited - edge with min cost */
                node[currentNode].visited = 1;
                count++;
                treeEdge[count][0] = node[currentNode].predecessor;
                treeEdge[count][1] = currentNode;

                /* calculate cost of MST */
                mstCost = mstCost + graphEdge[treeEdge[count][0]][treeEdge[count][1]];
        }
        return count;
  }

  int main() {
        int i, count;

        /* construct graph */
        buildGraph();
        count = buildTree();
        printf("MST is composed of below edges:\n");
        for (i = 1; i <= count; i++) {
                printf("%d<->%d\n", treeEdge[i][0], treeEdge[i][1]);
        }
        printf("\n");
        printf("Cost of Minimum Spanning Tree: %d\n", mstCost);
        return 0;
  }



  Output: (C Program To Implement MST Using Prim's Algorithm)
  jp@jp-VirtualBox:~/$ ./a.out
  Enter the no of vertices:6
  Edge(x to y)/(x<->x to exit):1 2
  Weight for the edge 1 to 2:1
  Edge(x to y)/(x<->x to exit):2 4
  Weight for the edge 2 to 4:2
  Edge(x to y)/(x<->x to exit):2 6
  Weight for the edge 2 to 6:7
  Edge(x to y)/(x<->x to exit):4 6
  Weight for the edge 4 to 6:5
  Edge(x to y)/(x<->x to exit):1 3
  Weight for the edge 1 to 3:6
  Edge(x to y)/(x<->x to exit):3 6
  Weight for the edge 3 to 6:3
  Edge(x to y)/(x<->x to exit):3 5
  Weight for the edge 3 to 5:4
  Edge(x to y)/(x<->x to exit):5 6
  Weight for the edge 5 to 6:8
  Edge(x to y)/(x<->x to exit):0 0

  MST is composed of below edges:
  1<->2
  2<->4
  4<->6
  6<->3
  3<->5
  Cost of Minimum Spanning Tree: 15



2 comments:

  1. excellently worked, can this program any be reduced further,because my professor wont believe me if i did this long program and executed by myself... u feel me right.

    ReplyDelete