Implement Kruskal’s algorithm to find a minimum weight spanning tree of an edge
ID: 3776570 • Letter: I
Question
Implement Kruskal’s algorithm to find a minimum weight spanning tree of an edge - weighted graph. A Java template has been provided containing an empty method MWST , which takes a single argument consisting of a weighted adjacency matrix for an edge - weighted graph. A correct implementation of the MWST function will use Kruskal’s algorithm to find a minimum weight spanning tree, then sum the weights of each selected edge to produce the return value.
Input: An n × n array G representing an edge-weighted graph.
Output: An integer value corresponding to the total weight of a minimum weight spanning tree of G.
import java.util.Arrays;
import java.util.Scanner;
import java.util.Vector;
import java.io.File;
//Do not change the name of the MWST class
public class MWST{
/* mwst(G)
Given an adjacency matrix for graph G, return the total weight
of all edges in a minimum weight spanning tree.
If G[i][j] == 0, there is no edge between vertex i and vertex j
If G[i][j] > 0, there is an edge between vertices i and j, and the
value of G[i][j] gives the weight of the edge.
No entries of G will be negative.
*/
static int MWST(int[][] G){
int numVerts = G.length;
/* Find a minimum weight spanning tree by any method */
/* (You may add extra functions if necessary) */
/* ... Your code here ... */
/* Add the weight of each edge in the minimum weight spanning tree
to totalWeight, which will store the total weight of the tree.
*/
int totalWeight = 0;
/* ... Your code here ... */
return totalWeight;
}
/* main()
Contains code to test the MWST function. You may modify the
testing code if needed, but nothing in this function will be considered
during marking, and the testing process used for marking will not
execute any of the code below.
*/
public static void main(String[] args){
Scanner s;
if (args.length > 0){
try{
s = new Scanner(new File(args[0]));
} catch(java.io.FileNotFoundException e){
System.out.printf("Unable to open %s ",args[0]);
return;
}
System.out.printf("Reading input values from %s. ",args[0]);
}else{
s = new Scanner(System.in);
System.out.printf("Reading input values from stdin. ");
}
int graphNum = 0;
double totalTimeSeconds = 0;
//Read graphs until EOF is encountered (or an error occurs)
while(true){
graphNum++;
if(graphNum != 1 && !s.hasNextInt())
break;
System.out.printf("Reading graph %d ",graphNum);
int n = s.nextInt();
int[][] G = new int[n][n];
int valuesRead = 0;
for (int i = 0; i < n && s.hasNextInt(); i++){
for (int j = 0; j < n && s.hasNextInt(); j++){
G[i][j] = s.nextInt();
valuesRead++;
}
}
if (valuesRead < n*n){
System.out.printf("Adjacency matrix for graph %d contains too few values. ",graphNum);
break;
}
long startTime = System.currentTimeMillis();
int totalWeight = MWST(G);
long endTime = System.currentTimeMillis();
totalTimeSeconds += (endTime-startTime)/1000.0;
System.out.printf("Graph %d: Total weight is %d ",graphNum,totalWeight);
}
graphNum--;
System.out.printf("Processed %d graph%s. Average Time (seconds): %.2f ",graphNum,(graphNum != 1)?"s":"",(graphNum>0)?totalTimeSeconds/graphNum:0);
}
}
Explanation / Answer
import java.util.collections;
import java.util.comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.scanner;
import java.util.stack;
public class kruskalsalgorithm
{
private List<Edge> edges;
private int numberofvertices;
public static final int MAX_VALUE=999;
private int visited[];
private int spanning_tree[][];
public kruskalalgorithm(int numberofvertices)
{
this.numberofvertices=numberofvertices;
edges=new LinkedList<Edge>();
visited = new int[this.numberofvertices + 1];
spanning_tree=new int[numberofvertices + 1][numberofvertices + 1];
}
public void kruskalalgorithm(int adjacencymatrix[][])
{
boolean finished=false;
for(int source=1;source < = numberofvertices; source++)
{
for(int destination = 1; destination <= numberofvertices; destination++)
{
if(adjacencymatrix[source][destination] != MAX_VALUE && source != destination)
{
Edge edge=new Edge();
edge.sourcevertex=source;
edge.destinationvertex=destination;
edge.weight=adjacencymatrix[source][destination];
adjacencymatrix[destination][source] = MAX_VALUE;
edges.add(edge);
}
}
}
Collections.sort(edges, new EdgeComparator());
CheckCycle checkcycle = new CheckCycle();
for(Edge edge : edges)
{
spanning_tree[edge.sourcevertex][edge.destinationvertex]=edge.weight;
spanning_tree[edge.destinationvertex][edge.sourcevertex]=edge.weight;
if(checkcycle.checkcycle(spanning_tree,edge.sourcevertex))
{
spanning_tree[edge.sourcevertex][edge.destinationvertex] = 0;
spanning_tree[edge.destinationvertex][edge.sourcevertex] = 0;
edge.weight = -1;
continue;
}
visited[edge.sourcevertex]=1;
visited[edge.destinationvertex]=1;
for(int 1=0;i<visited.length;i++)
{
if(visited[i]==0)
{
finished= false;
break;
}
else
{
finished=true;
}
}
if(finished)
break;
}
system.out.println("the spanning tree is:");
for(int i=1;i<numberofvertices;i++)
system.out.println(" " +i);
system.out.println();
for(int source=1;source<=numberofvertices;sources++)
{
system.out.print(source + " ");
int visited[] =new int[numberofnodes+1];
int element=source;
int i=source;
visited[source]=1;
stack.push(source);
while(!stack.isEmpty())
{
element=stack.peek();
i=element;
while(i<=numberofnodes)
{
if(adjacencymatrix[element][i]>=1 && visited[i] ==1)
{
if(stack.contains(i))
{
cyclepresent = true;
return cyclepresent;
}
}
if(adjacencymatrix[element][i]>=1 && visited[i] ==0 )
{
stack.push(i);
visited[i]=1;
adjacencymatrix[element][i]=0;
adjacencymatrix[i][element]=0;
element=i;
i=1;
continue;
}
i++;
}
stack.pop();
}
return cyclepresent;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.