Code Scrappers


Kruskals C Program


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

                    int p[10], c[10][10];

                    int search(int);

                    int u(int, int);


                    int main()

                    {
                            int i, j, n, count = 1, x, y, a, b, minimum, minc;

                            printf("Kruskals algorithm \n");

                            printf("enter size of matrix:\t");

                            scanf("%d",&n);

                            printf("\n enter the elements of 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] = 9999;
                                            }
                                    }
                            }


                            while(count<n)

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

                                                            a = x = i;

                                                            b = y = j;
                                                    }
                                            }
                                    }

                                    x = search(x);

                                    y = search(y);

                                    if(u(x, y))

                                    {
                                            printf("\n%d edge(%d, %d) = %d",count++, a, b, minimum);

                                            minc = minc + minimum;
                                    }

                                    c[a][b] = c[b][a] = 9999;

                           }

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

                          return 0;

                  }

                  int search(int i)

                  {
                        while(p[i])
                        {
                              i = p[i];
                        }

                        return i;
                  }

                  int u(int i, int j)

                  {
                        if(i != j)
                        {
                              p[j] = i;

                              return 1;
                        }

                        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