Code Scrappers


Prims Algorithm - C program


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

                  int main()

                  {
                          int n, ne = 1, i, j;

                          int c[10][10], traversed[10] = {0};

                          int minimum, minc = 0, a, b, x, y;

                          printf("enter no. of vertices\n");

                          scanf("%d",&n);

                          printf("enter matrix\n");

                          for(i=1;i<=n;i++)
                          {
                                  for(j=1;j<=n;j++)
                                  {
                                          scanf("%d",&c[i][j]);

                                          if(c[i][j] == 0)
                                          {
                                                  c[i][j] = 999;
                                          }
                                  }
                          }

                          traversed[1] = 1;

                          while(ne < n)
                          {
                                  minimum = 999;

                                  for(i=1;i<=n;i++)
                                  {
                                          for(j=1;j<=n;j++)
                                          {
                                                  if(c[i][j] < minimum)
                                                  {
                                                          if(traversed[i] != 0)
                                                          {
                                                                  minimum = c[i][j];

                                                                  a = x = i;

                                                                  b = y = j;
                                                        }
                                                }
                                        }
                                }

                                if(traversed[x] == 0 || traversed[y] == 0)
                                {
                                        printf("%d edge(%d, %d) = %d\n",ne++, a, b, minimum);

                                        minc = minc + minimum;

                                        traversed[b] = 1;
                                }

                                c[a][b] = c[b][a] = 999;

                        }

                        printf("\n total cost = %d",minc);

                        return 0;
                  }
              



Output

              enter the no. of vertices
              4
              enter the matrix
              0
              10
              0
              2
              10
              0
              6
              0
              0
              6
              0
              8
              2
              0
              8
              0

              1 edge(1, 4) : 2
              2 edge(4, 3) : 8
              3 edge(3, 2) : 6

              total cost = 16