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



node_ptr create_list()
{
    node_ptr header_node = (node_ptr)malloc(sizeof(struct node));
    header_node->to_vertex = -1;
    header_node->weight = -1;
    header_node->next = NULL;
    return header_node;
}

void destroy_list(node_ptr header_node)
{
    node_ptr current = header_node; /* Dynamically allocated memory to header_node node */
    node_ptr temp;

    while(current){
        temp = current;
        current = current->next;
        free(temp);/* Free the dynamically allocated memory */

    }
}

void insert_at_front(node_ptr header_node, int w, int to_vertec)
{
    node_ptr new_node = (node_ptr)malloc(sizeof(struct node));/* Dynamically allocated memory to new_node */
    new_node->to_vertex = to_vertec;
    new_node->weight = w;
    new_node->next = header_node->next;
    header_node->next = new_node;
}

span_ptr create_span_list()
{
    span_ptr span_header = (span_ptr)malloc(sizeof(struct span_tree));
    span_header->total_weight = -1;
    span_header->next = NULL;
    return span_header;
}

void destroy_span_list(span_ptr min)/* Function to destroy the span_list */
{
    span_ptr current = min;
    span_ptr temp;

    while(current){ /*while it's not the end,keep going*/
        temp = current;
        current = current->next;
        free(temp); /*free it one by one*/
    }
}

void span_insert_at_front(span_ptr min, int weight)
{
    span_ptr new_node = (span_ptr)malloc(sizeof(struct span_tree));
    new_node->total_weight = weight;
    new_node->next = min->next;
    min->next = new_node;
}

/*============functions for table====================*/

table create_table(int max_span)
{
    table t;
    
    t = (table)malloc(max_span * sizeof(struct table_property));
    return t;
}

void destroy_table(table t)
{
    free(t);
}

void start_table(table t, int max_span)
{
    int i;
    
    for(i=0; i<max_span; i++){   /*create the dummy header node*/
        t[i].known = 0;
        t[i].distance = infinity;
        t[i].path = Not_a_Vertex;
    }
}

void set_initial_vertex(table t, int initial_vertex)
{
    t[initial_vertex].distance = 0; /*set the start vertex to be zero*/
}

int nearest_unknown_vertex(table t, int max_span)
{
    int i;
    int v = Not_a_Vertex;
    int dist = infinity;

    for(i=0; i<max_span; i++){
        if(!t[i].known && t[i].distance < dist){
            dist = t[i].distance;
            v = i;
        }
    }
    return v;
}

int find_next(table t, int max_span)
{
    int i, what_next=0;

    for(i=0; i<max_span; i++){
        if(!t[i].known && t[i].distance == infinity){
            what_next = i;
            break;
        }
    }
    return what_next;
}

int find_maximum(span_ptr min)
{
    int maximum = 0;
    span_ptr current;

    for(current=min->next; current; current=current->next){
        if(current->total_weight > maximum){
            maximum = current->total_weight;
        }
    }
    return maximum;
}

/*====================prims algorithm===============================*/

void prims(table t, node_ptr g[], int max_vertex, span_ptr span_tree)
{
    int v;
    int w;
    int number_of_vertex = 0;
    node_ptr current;

    span_insert_at_front(span_tree, 0);    

    while(1){

        v = nearest_unknown_vertex(t, max_vertex);
        printf("Nearest Vertex:%d\n",v);


        if (v == Not_a_Vertex){
            if(number_of_vertex == max_vertex){
                break;
            }else{
                v = find_next(t, max_vertex);
                set_initial_vertex(t,v);
                span_insert_at_front(span_tree, 0);
            }
        }
    
        t[v].known = 1;            
        number_of_vertex++;        
        span_tree->next->total_weight += t[v].distance;    

    
        for(current = g[v]->next; current; current=current->next){
            w = current->to_vertex;
            if(!t[w].known){
                if(current->weight < t[w].distance){
                    /* Update the all t[w] value in the table */
                    t[w].distance =    current->weight;
                    /*printf("the current weight:%d\n",w);*/
                    t[w].path = v;
                }
            }
        }

    }
}
--------------------------------------------------------------------------
#ifndef _LIST_H
#define _LIST_H

#define Not_a_Vertex (-1)
#define infinity (9999)

typedef struct node *node_ptr;
typedef struct table_property *table;
typedef struct span_tree *span_ptr;

struct node
{
    int to_vertex;
    int weight;
    node_ptr next;
};

struct table_property
{
    int known; /*to store the know vertex*/
    int distance;/*how far are they*/
    int path;
};

struct span_tree
{
    int total_weight; /*this is to store some disconnected graphs weight*/
    span_ptr next;
};

node_ptr create_list();

void destroy_list(node_ptr header_node);

void insert_at_front(node_ptr header_node, int w, int to_vertec);

span_ptr create_span_list();

void destroy_span_list(span_ptr min);

void span_insert_at_front(span_ptr min, int weight);

table create_table(int max);

void destroy_table(table t);

void start_table(table t, int max);

void set_initial_vertex(table t, int initial_vertex);

int nearest_unknown_vertex(table t, int max);

int find_next(table t, int max);

void prims(table t, node_ptr g[], int max_vertex, span_ptr span_tree);

int find_maximum(span_ptr min);


#endif
----------------------------------------------------------
#include <stdio.h>
#include "list.h"

int main(){
    int i;
    int number_of_vertex, number_of_edges;
    int weight, smallest, biggest, maximum;
    table t;
    node_ptr g[10000];
    span_ptr span_list;    

    scanf("%d %d", &number_of_vertex, &number_of_edges);

    /* Create list and initialise g[i] */
    for(i=0; i<number_of_vertex; i++){
        g[i] = create_list();
    }

    /* Read graph */    
    for(i=0; i<number_of_edges; i++){
        scanf("%d %d %d", &weight, &smallest, &biggest);
        insert_at_front(g[smallest], weight, biggest);
        insert_at_front(g[biggest], weight, smallest);
    }

    /* Table is created and initialised */
    t = create_table(number_of_vertex);

    start_table(t, number_of_vertex);

    /* Set the starting vertex as vertex 0 */
    set_initial_vertex(t, 0);

    /* span_list is created */
    span_list = create_span_list();

    /* Prims algorithm process and record them into the table */
    prims(t, g, number_of_vertex, span_list);

    /* Get and printf the maximum value from span_list */
    maximum = find_maximum(span_list);
    printf("%d\n", maximum);

    /* Destroy the adjacency list, table and span_list */
    for(i=0; i<number_of_vertex; i++){
        destroy_list(g[i]);
    }

    destroy_table(t);/*destroy the table after successfully get the minimum tree*/

    destroy_span_list(span_list);/*destroy the span_list after successfully get the minimum tree*/

    return 0;

}