C Program to find MST(Minimum Spanning Tree) using Prim's Algorithm

C Program to find MST(Minimum Spanning Tree) using Prim's Algorithm

How to write a C Program to find MST(Minimum Spanning Tree) using Prim's Algorithm in C Programming Language ?


Solution:


/*
 * C Program to find MST(Minimum Spanning Tree) using Prim's Algorithm
 */

#include <iostream>

using namespace std;


int c = 0,temp1 = 0,temp = 0, MAX = 2222;

struct node
{
    int fr,to,cost;
}p[2222];


int main()
{   int tamano, vertices, arcos, n1, n2, costo;
    cout << "Numero de nodos: " << endl;
    cin >> tamano;
    cin >> arcos;
    vertices = tamano-1;

    int a[tamano];

    for (int i = 0; i < tamano; i++)
    {
        a[i] = 0; // CHANGE 0 por MAX
    }

    int b[tamano][tamano];

    for(int k = 0; k < tamano; k++) {
       for (int i = 0; i < tamano; ++i)
       {
           b[k][i] = 0;
       }
    }
    
    cout << "Costo de arcos:" << endl;

    for(int k = 0; k < arcos; k++) {
            cin >> n1 >> n2 >> costo;
            b[n1][n2] = costo;
            b[n2][n1] = costo;
    }

    for(int k = 0; k < tamano; k++) {
       for (int i = 0; i < tamano; ++i)
       {
           cout << b[k][i] << " ";
       }
       cout << endl;
    }

    //Algoritmo:
    a[0] = 1;
    while (c < vertices)
    {
        int min = 999;
        for (int i = 0; i < tamano; i++)
        {
            if (a[i] == 1)
            {
                for (int j = 0; j < tamano; )
                {
                    if (b[i][j] >= min || b[i][j] == 0)
                    {
                        j++;
                    }
                    else if (b[i][j] < min)
                    {
                        min = b[i][j];
                        temp = i;
                        temp1 = j;
                    }
                }
            }
        }
        a[temp1] = 1;
        p[c].fr = temp;
        p[c].to = temp1;
        p[c].cost = min;
        c++;       
        b[temp][temp1] = b[temp1][temp]=1000;
    }
    for (int k = 0; k < vertices; k++)
    {
        cout<<"source node:"<<p[k].fr<<endl;
        cout<<"destination node:"<<p[k].to<<endl;
        cout<<"weight of node"<<p[k].cost<<endl;
    }

}


Learn More :