#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;
}