(20 points) Consider the following undirected weighted graph. 34 36 24 35 25 39
ID: 3811335 • Letter: #
Question
(20 points) Consider the following undirected weighted graph. 34 36 24 35 25 39 19 23 12 21 33 30 (a) Give the list of edges in the minimum spanning tree in the order that Kruskal's algorithm inserts them. Please implement the Kruskal's algorithm. Include screenshots of the program running and submit your java code in a separate file. (b) Give the list of edges in the minimum spanning tree in the order that Prim's algorithm inserts them, assuming that it starts at vertex F. Please implement the Prim's algorithm. Include screenshots of the program running and submit your java code in a separate file.Explanation / Answer
//kruskal implementation
// Java program for Kruskal's algorithm to find Minimum Spanning Tree
// of a given connected, undirected and weighted graph
import java.util.*;
import java.lang.*;
import java.io.*;
class Graph
{
// A class to represent a graph edge
class Edge implements Comparable<Edge>
{
int src, dest, weight;
// Comparator function used for sorting edges based on
// their weight
public int compareTo(Edge compareEdge)
{
return this.weight-compareEdge.weight;
}
};
// A class to represent a subset for union-find
class subset
{
int parent, rank;
};
int V, E; // V-> no. of vertices & E->no.of edges
Edge edge[]; // collection of all edges
// Creates a graph with V vertices and E edges
Graph(int v, int e)
{
V = v;
E = e;
edge = new Edge[E];
for (int i=0; i<e; ++i)
edge[i] = new Edge();
}
// A utility function to find set of an element i
// (uses path compression technique)
int find(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(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++;
}
}
// The main function to construct MST using Kruskal's algorithm
void KruskalMST()
{
Edge result[] = new Edge[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
for (i=0; i<V; ++i)
result[i] = new Edge();
// 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
Arrays.sort(edge);
// Allocate memory for creating V ssubsets
subset subsets[] = new subset[V];
for(i=0; i<V; ++i)
subsets[i]=new subset();
// Create V subsets with single elements
for (int v = 0; v < V; ++v)
{
subsets[v].parent = v;
subsets[v].rank = 0;
}
i = 0; // Index used to pick next edge
// 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
Edge next_edge = new Edge();
next_edge = 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
}
// print the contents of result[] to display the built MST
System.out.println("Following IS the order of the edges that are constructed MST");
for (i = 0; i < e; ++i)
System.out.println(result[i].src+" -- "+result[i].dest+" == "+
result[i].weight);
}
// Driver Program
public static void main (String[] args)
{
int V = 9; // Number of vertices in graph
int E = 18; // Number of edges in graph
Graph graph = new Graph(V, E);
//here in this graph
//A - 0
//B - 1
//C - 2
//D - 3
//E - 4
//F - 5
//G - 6
//H - 7
//I - 8
// add edge
graph.edge[0].src = 0;//A
graph.edge[0].dest = 1;//B
graph.edge[0].weight = 22;
// add edge
graph.edge[1].src = 0;//A
graph.edge[1].dest = 2;//C
graph.edge[1].weight = 9;//
graph.edge[2].src = 0;//A
graph.edge[2].dest = 3;//D
graph.edge[2].weight = 12;
graph.edge[3].src = 1;//B
graph.edge[3].dest = 2;//C
graph.edge[3].weight = 35;
graph.edge[4].src = 2;//C
graph.edge[4].dest = 3;//D
graph.edge[4].weight = 4;
graph.edge[5].src = 1;//B
graph.edge[5].dest = 7;//F
graph.edge[5].weight = 36;
graph.edge[6].src = 1 ;//B
graph.edge[6].dest = 7;//H
graph.edge[6].weight = 34;
graph.edge[7].src = 2;//C
graph.edge[7].dest = 5;//F
graph.edge[7].weight = 42;
graph.edge[8].src = 2;//C
graph.edge[8].dest = 4;//E
graph.edge[8].weight = 65;
graph.edge[9].src = 3;//D
graph.edge[9].dest = 4;//E
graph.edge[9].weight = 33;
graph.edge[10].src = 3;//D
graph.edge[10].dest = 8;//I
graph.edge[10].weight = 30;
graph.edge[11].src = 4;//E
graph.edge[11].dest = 6;//G
graph.edge[11].weight = 23;
graph.edge[12].src = 5;//F
graph.edge[12].dest = 6;//G
graph.edge[12].weight = 39;
graph.edge[13].src = 5;//F
graph.edge[13].dest = 4;//E
graph.edge[13].weight = 18;
graph.edge[14].src = 5;//F
graph.edge[14].dest = 7;//H
graph.edge[14].weight = 24;
graph.edge[15].src = 6;//G
graph.edge[15].dest = 7;//H
graph.edge[15].weight = 25;
graph.edge[16].src = 6;//G
graph.edge[16].dest = 8;//I
graph.edge[16].weight = 21 ;
graph.edge[17].src = 7;//H
graph.edge[17].dest = 8;//I
graph.edge[17].weight =19 ;
graph.KruskalMST();
}
}
output:-
run:
Following IS the order of the edges that are constructed MST
2 -- 3 == 4
0 -- 2 == 9
5 -- 4 == 18
7 -- 8 == 19
6 -- 8 == 21
0 -- 1 == 22
4 -- 6 == 23
3 -- 8 == 30
//prims...
import java.util.*;
import java.lang.*;
import java.io.*;
class MST
{
// Number of vertices in the graph
private static final int V=9;
// A utility function to find the vertex with minimum key
// value, from the set of vertices not yet included in MST
int minKey(int key[], Boolean mstSet[])
{
// Initialize min value
int min = Integer.MAX_VALUE, min_index=-1;
for (int v = 0; v < V; v++)
if (mstSet[v] == false && key[v] < min)
{
min = key[v];
min_index = v;
}
return min_index;
}
// A utility function to print the constructed MST stored in
// parent[]
void printMST(int parent[], int n, int graph[][])
{
System.out.println("Edge Weight");
for (int i = 1; i < V; i++)
System.out.println(parent[i]+" - "+ i+" "+
graph[i][parent[i]]);
}
// Function to construct and print MST for a graph represented
// using adjacency matrix representation
void primMST(int graph[][])
{
// Array to store constructed MST
int parent[] = new int[V];
// Key values used to pick minimum weight edge in cut
int key[] = new int [V];
// To represent set of vertices not yet included in MST
Boolean mstSet[] = new Boolean[V];
// Initialize all keys as INFINITE
for (int i = 0; i < V; i++)
{
key[i] = Integer.MAX_VALUE;
mstSet[i] = false;
}
// Always include first 1st vertex in MST.
key[0] = 0; // Make key 0 so that this vertex is
// picked as first vertex
parent[0] = -1; // First node is always root of MST
// The MST will have V vertices
for (int count = 0; count < V-1; count++)
{
// Pick thd minimum key vertex from the set of vertices
// not yet included in MST
int u = minKey(key, mstSet);
// Add the picked vertex to the MST Set
mstSet[u] = true;
// Update key value and parent index of the adjacent
// vertices of the picked vertex. Consider only those
// vertices which are not yet included in MST
for (int v = 0; v < V; v++)
{
// graph[u][v] is non zero only for adjacent vertices of m
// mstSet[v] is false for vertices not yet included in MST
// Update the key only if graph[u][v] is smaller than key[v]
//System.out.println(u+" "+v);
if (graph[u][v]!=0 && mstSet[v] == false &&
graph[u][v] < key[v])
{
parent[v] = u;
key[v] = graph[u][v];
}
}
}
// print the constructed MST
printMST(parent, V, graph);
}
public static void main (String[] args)
{
//given graph...
MST t = new MST();
//here in this graph
//A - 4
//B - 5
//C - 6
//D - 7
//E - 8
//F - 0
//G - 1
//H - 2
//I - 3
//vertices : 9
//edges : 18
System.out.println("Mst final output:");
int graph[][] = new int[][] {{0,39,24,0,0,36,42,0,18},
{39,0,25,21,0,0,0,0,23},
{24,25,0,19,0,34,0,0,0},
{0,21,19,0,0,0,0,30,0},
{0,0,0,0,0,22,9,12,0},
{36,0,34,0,22,0,35,0,0},
{42,0,0,0,9,35,0,4,65},
{0,0,0,30,12,0,4,0,33},
{18,23,0,0,0,0,65,33,0}
};
// Print the solution
t.primMST(graph);
}
}
output:-
run:
Mst final output:
Edge Weight
8 - 1 23
3 - 2 19
1 - 3 21
6 - 4 9
4 - 5 22
7 - 6 4
3 - 7 30
0 - 8 18
BUILD SUCCESSFUL (total time: 0 seconds)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.