Use a modification of Kruskals Algorithm to find the maximum

Use a modification of Kruskal\'s Algorithm to find the maximum spanning tree for the weighted graph. Give the total weight of the maximum spanning tree. What is the total weight of the maximum spanning tree? The total weight is .

Solution

Here is the program for maximum spanning tree using Modification in Kruskal\'s Algorithm which will give the name of the edges.

I have named the vertex as C=0,A=1,B=2,D=3,E=4 in the program.

// C++ program for Modified Kruskal\'s algorithm to find Maximum Spanning Tree
// of a given connected, undirected and weighted graph
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// a structure to represent a weighted edge in the graph
struct Edge
{
int src, dest, weight;
};

// a structure to represent the graph
struct Graph
{
// V is Number of vertices, E is Number of edges
int V, E;

// Here, Graph is represented as an array of edges.And since the graph is
// undirected, the edge from src to dest is also edge from dest
// to src. So, both will be counted as 1 edge here.
struct Edge* edge;
};

// A graph with V vertices and E edges is created
struct Graph* createGraph(int V, int E)
{
struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph) );
graph->V = V;
graph->E = E;

graph->edge = (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );

return graph;
}

// A structure which represents a subset for union-find
struct subset
{
int parent;
int rank;
};

// A utility function to find set of an element i
// (uses path compression technique)
int find(struct subset subsets[], int i)
{
// find root and make root as parent of i (path compression)
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);

return subsets[i].parent;
}

// A function that does union of two sets of x and y
// (uses union by rank)
void Union(struct subset subsets[], int x, int y)
{
int xroot = find(subsets, x);
int yroot = find(subsets, y);

// Attach smaller rank tree under root of high rank tree
// (Union by Rank)
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;

// If ranks are same, then make one as root and increment
// its rank by one
else
{
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}

// Compare two edges according to their weights.
// Used in qsort() for sorting an array of edges
int myComp(const void* a, const void* b)
{
struct Edge* a1 = (struct Edge*)a;
struct Edge* b1 = (struct Edge*)b;
return a1->weight > b1->weight;
}

// The main function to construct MST using Kruskal\'s algorithm
void KruskalMST(struct Graph* graph)
{
int V = graph->V;
struct Edge result[V]; // Tnis will store the resultant MST
int e = 0; // An index variable, used for result[]
int i = 0; // An index variable, used for sorted edges

// Step 1: Sort all the edges in non-decreasing order of their weight
// If we are not allowed to change the given graph, we can create a copy of
// array of edges
qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);

// Allocate memory for creating V ssubsets
struct subset *subsets =
(struct subset*) malloc( V * sizeof(struct subset) );

// Create V subsets with single elements
for (int v = 0; v < V; ++v)
{
subsets[v].parent = v;
subsets[v].rank = 0;
}

// Number of edges to be taken is equal to V-1
while (e < V - 1)
{
// Step 2: Pick the smallest edge. And increment the index
// for next iteration
struct Edge next_edge = graph->edge[i++];

int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);

// If including this edge does\'t cause cycle, include it
// in result and increment the index of result for next edge
if (x != y)
{
result[e++] = next_edge;
Union(subsets, x, y);
}
// Else discard the next_edge
}

// prints the contents of result[] to display the built Maximum Spanning Tree
printf(\"Following are the edges in the constructed MST\ \");
for (i = 0; i < e; ++i)
printf(\"%d -- %d == %d\ \", result[i].src, result[i].dest,
result[i].weight);
return;
}

// Driver program to test the given above functions
int main()
{
int V = 5; // Number of vertices present in graph
int E = 8; // Number of edges in present in graph
struct Graph* graph = createGraph(V, E);


// add edge 0-1
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -71;

// add edge 0-2
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = -78;

// add edge 0-3
graph->edge[2].src = 0;
graph->edge[2].dest = 3;
graph->edge[2].weight = -83;
  
// add edge 0-4
graph->edge[5].src = 0;
graph->edge[5].dest = 4;
graph->edge[5].weight = -73;

// add edge 1-2
graph->edge[3].src = 1;
graph->edge[3].dest = 2;
graph->edge[3].weight = -76;
  
  
// add edge 1-4
graph->edge[7].src = 1;
graph->edge[7].dest = 4;
graph->edge[7].weight = -61;

// add edge 2-3
graph->edge[4].src = 2;
graph->edge[4].dest = 3;
graph->edge[4].weight = -64;
  
  
// add edge 3-4
graph->edge[6].src = 3;
graph->edge[6].dest = 4;
graph->edge[6].weight = -67;

KruskalMST(graph);

return 0;
}

Which gives the output as :

Following are the edges in the constructed MST
0 -- 3 == -83
0 -- 2 == -78
1 -- 2 == -76
0 -- 4 == -73

Here i have added negative sign so that it will calculate Maximum weights. Now on counting total weight is 310.

And the maximum spanning tree is the 2nd picture from question.