#include<stdio.h> 
#define NODENUM 7 


typedef struct { 
    int n;                           // note amount 
    float arcs[NODENUM][NODENUM];    // edges info 
} Graph; 

typedef struct{ 
    int start, end;             // start point && end point 
    float weight;               // wright of the edge 
} Edge; 

Edge edge[6]; 

#define MAX 10000 

void prim(Graph * pgraph, Edge edge[]) { 
    int i, j, min, vx, vy; 
    float weight, minweight; Edge ed; 

    for (i = 0; i < pgraph->n-1; i++) { 
        edge[i].start = 0; 
        edge[i].end = i+1; 
        edge[i].weight = pgraph->arcs[0][i+1]; 
    } 

    for (i = 0; i < pgraph->n-1; i++) {              
        minweight = MAX;  min = i; 
        for (j = i; j < pgraph->n-1; j++)  // get the minweght edge 
            if(edge[j].weight < minweight) { 
                minweight = edge[j].weight; 
                min = j; 
            } 

      
        ed = edge[min];  
        edge[min] = edge[i];   
        edge[i] = ed; 
        vx = edge[i].end;          

        for(j = i+1; j < pgraph->n-1; j++) { 
            vy=edge[j].end; weight = pgraph->arcs[vx][vy]; 
            if (weight < edge[j].weight) { 
                edge[j].weight = weight;  
                edge[j].start = vx; 
            } 
        } 
    } 
} 

Graph graph = { 
    7, 
    {{0  ,8  ,9  ,MAX,MAX,MAX,MAX}, 
     {8  ,0  ,15 ,6  ,MAX,12 ,MAX}, 
     {9  ,15 ,0  ,MAX,13 ,MAX,14 }, 
     {MAX,6  ,MAX,0  ,8  ,8  ,MAX}, 
     {MAX,MAX,13 ,8  ,0  ,MAX,7  }, 
     {MAX,12 ,MAX,8  ,MAX,0  ,8  }, 
     {MAX,MAX,14 ,MAX,7  ,8  ,0  } 
    
    } 
}; 

int main(){ 
    int i; 
    prim(&graph,edge); 
    for (i = 0; i < graph.n-1; i++) 
    { 
            printf("(%d", edge[i].start + 1); 
printf(" - > "); 
printf("%d   : %.0f)\n",edge[i].end + 1, edge[i].weight); 
} 
    return 0; 
}