#include
#include
struct edge
{
int source;
int target;
int weight;
};
/* A graph is an array of edges. */
typedef struct edge* graph;
//for compare functions
typedef int (*compfn)(const void*, const void*);
//Function Prototypes
void makeset(int i, int parent []);
int kruskal_mst(graph g, int num_edges, int num_vertices, graph tree);
int compare(struct edge *left, struct edge *right);
void link (int x, int y, int parent[]);
int find (int x, int parent[]);
int main(int argc, char* argv[])
{
int num_edges, num_vertices, i, num_edges_in_tree;
graph g;
FILE* f;
graph tree;
f = fopen(argv[1], "r");
/* Read in the number of edges from the file */
fscanf(f, "%d\n", &num_edges);
/* Read in the number of vertices from the file */
fscanf(f, "%d\n", &num_vertices);
/* Read the graph from the file */
g = (graph)malloc(num_edges * sizeof(struct edge));
for (i = 0; i != num_edges; ++i)
fscanf(f, "%d-%d-%d\n", &g[i].source, &g[i].weight, &g[i].target);
/* allocate memory for the tree */
tree = (graph)malloc(num_vertices * sizeof(struct edge));
/* Find the minimum spanning tree using Kruskal's algorithm */
num_edges_in_tree = kruskal_mst(g, num_edges, num_vertices, tree);
printf("%d", num_edges_in_tree);
/* Print out the minimum spanning tree */
for (i = 0; i != num_edges_in_tree; ++i)
printf("%d-%d-%d\n", tree[i].source, tree[i].weight, tree[i].target);
return 0;
}
int kruskal_mst(graph g, int num_edges, int num_vertices, graph tree)
{
int j = 0;
int i;
int parent[num_vertices];
// start with empty set
for(i = 0; i < num_vertices; i++) //for each vertex
{
makeset(i, parent); // makes singleton sets
}
qsort(g, num_edges, sizeof(struct edge), (compfn)compare); // Sort Edges into new graph
for (i = 0; i < num_edges ; i++) //for each edge
{
if (find(g[i].source, parent) != find(g[i].target, parent))
{
tree[j] = g[i];
link(g[i].source, g[i].target, parent); //union
j++;
}
}
return j;
}
//makes array of parents of each vertex
void makeset(int i, int parent[])
{
parent[i] = i;
}
// compare compares two inputs, if 12 ret 1, if 1=2 ret 0
int compare (struct edge *left, struct edge *right)
{
if (left->weight < right->weight)
return -1;
if (left->weight > right->weight)
return 1;
else
return 0;
}
void link (int y, int x, int parent[])
{
parent[x] = parent[y];
}
int find(int x, int parent[])
{
if (parent[x] == x){
return x;}
else
return find(parent[x], parent);
}
