is kruskal algorithm a spanning tree? code example
Example: Kruskal's Algorithm for minimum spanning tree
#include
#include
typedef struct node
{
int source;
int destination;
int weight;
} Edge;
typedef struct Graph
{
int num_of_vertex;
int num_of_edge;
Edge *edge;
} Graph;
typedef struct subset
{
int parent;
int rank;
} Subset;
Graph *create_graph (int V, int E)
{
Graph *new_graph = (Graph *) malloc (sizeof (Graph));
new_graph -> num_of_vertex = V;
new_graph -> num_of_edge = E;
new_graph -> edge = (Edge *) malloc (new_graph -> num_of_edge * sizeof (Edge));
return new_graph;
}
int find_set (Subset subset[], int i)
{
if (subset[i]. parent != i)
{
subset[i]. parent = find_set (subset, subset[i]. parent);
}
return subset[i]. parent;
}
void Union (Subset subset[], int x, int y)
{
int x_parent = find_set (subset, x);
int y_parent = find_set (subset, y);
if (subset [x_parent]. rank < subset [y_parent]. rank)
{
subset [x_parent]. parent = y_parent;
subset [y_parent]. rank += 1;
}
else
{
subset [y_parent]. parent = x_parent;
subset [x_parent]. rank += 1;
}
}
int comparison (const void *a, const void *b)
{
Edge *a1 = (Edge *) a;
Edge *b1 = (Edge *) b;
return a1 -> weight > b1 -> weight;
}
void KruskalMST (Graph *graph)
{
int V = graph -> num_of_vertex;
Edge result [V];
qsort (graph -> edge, graph -> num_of_edge, sizeof (graph -> edge [0]), comparison);
Subset *subset = (Subset *) malloc (V * sizeof (Subset));
for (int i = 0; i < V; i++)
{
subset [i]. parent = i;
subset [i]. rank = 0;
}
int e = 0;
int i = 0;
while (e < V-1)
{
Edge temp_edge = graph -> edge[i];
i++;
int parent_src = find_set (subset, temp_edge. source);
int parent_dest = find_set (subset, temp_edge. destination);
if (parent_src != parent_dest)
{
result [e] = temp_edge;
e++;
Union (subset, parent_src, parent_dest);
}
}
printf("Following are the edges in the constructed MST\n");
for (i = 0; i < e; i++)
printf("%d -- %d == %d\n", result[i]. source, result[i]. destination, result[i]. weight);
}
void main()
{
int V = 4;
int E = 5;
Graph* graph = create_graph(V, E);
// add edge 0-1
graph->edge[0].source = 0;
graph->edge[0].destination = 1;
graph->edge[0].weight = 10;
// add edge 0-2
graph->edge[1].source = 0;
graph->edge[1].destination = 2;
graph->edge[1].weight = 6;
// add edge 0-3
graph->edge[2].source = 0;
graph->edge[2].destination = 3;
graph->edge[2].weight = 5;
// add edge 1-3
graph->edge[3].source = 1;
graph->edge[3].destination = 3;
graph->edge[3].weight = 15;
// add edge 2-3
graph->edge[4].source = 2;
graph->edge[4].destination = 3;
graph->edge[4].weight = 4;
KruskalMST(graph);
}