Prim.cpp

#include <stdio.h>

void addEdge(int source,int target,int weight);

int graph[5][5]={0};

int main()
{
    //Init
    int parent[5]; //I'th parent
    int cost[5]; //minimal cost of connect I'th vertex
    bool selected[5]; //is I in MST or not 
    for (int i=0;i<=4;i++)
    {
        cost[i]=99999;
        selected[i]=false;
    }

    addEdge(0,1,2);
    addEdge(0,3,6);
    addEdge(1,2,3);
    addEdge(1,3,8);
    addEdge(1,4,5);
    addEdge(2,4,7);
    addEdge(3,4,9);

    //start from node 4
    parent[4]=-1; //it's parent is root
    cost[4]=0; //connect root doesn't cost
 
    //prim start
    for (int count=0; count <= 4; count++)
    {
        //pick minimun cost value index
        int min=99999,index;        
        for(int i=0;i<=4;i++)
        {
            if(selected[i]==false&&cost[i]<min)
            {
                min=cost[i];
                index=i;
            }
        }

        selected[index]=true;

        //update each connected vertex cost and set vertex parent
        for (int i=0;i<=4;i++)
        {
            if (graph[index][i]!=0 && selected[i]==false && graph[index][i]<cost[i])
            {
                parent[i]=index;
                cost[i]=graph[index][i];
            }
        }
    }

    printf("Node Node Weight\n");
    for (int i = 0; i <= 4; i++)
    {
        if(parent[i]==-1) printf("%2d - root\n",i);
        else printf("%2d - %2d %4d \n", i,parent[i], cost[i]);
    }
    return 0;
}

void addEdge(int source,int target,int weight){
    graph[source][target]=weight;
    graph[target][source]=weight;
}