Class Main
package fwn.knzw.lab;import fwn.knzw.lab.classes.Kruskal;import fwn.knzw.lab.classes.Prim;public class MST_test { public static void main(String[] args) { MST_test mst = new MST_test(); //Prim p = new Prim(); Kruskal k = new Kruskal(); } } Class Edge
package fwn.knzw.lab.classes;public class Edge { public int start;//start node public int end;//end node public double cost;//cost} Class Prim
package fwn.knzw.lab.classes;import java.util.ArrayList;import java.util.Arrays;import java.util.Scanner;import fwn.knzw.lab.MST_test;public class Prim { private static double INFINITY = 99999999.99;//define an infinity private double cost[][];//a matrix to store the weight of edges private ArrayList edge = new ArrayList ();//a list to store edges private int[] near ;//to mark if a point is in the result set private double minCost = 0.0;//the minimum cost private int n;//the number of nodes public Prim(){ init(); prim(); print(); } //to initiate the graph public void init(){ System.out.println("--MST Prim's alogrithm-------"); Scanner scan = new Scanner(System.in); int p,q; double w; //input the number of nodes System.out.println("Input the number of nodes:"); n = scan.nextInt(); //build matrix 'cost' and array 'near' cost = new double[n][n]; near = new int[n]; //initiate the cost matrix with INFINITY for(int i = 0; i < n; ++i){ Arrays.fill(cost[i],INFINITY); } //input the edges System.out.println("Input the graph(-1,-1,-1 to exit):"); while(true){ p = scan.nextInt(); q = scan.nextInt(); w = scan.nextDouble(); if(p < 0 || q < 0 || w < 0){ break; } cost[p][q] = w; cost[q][p] = w; } //choose the first smallest edge and add it to the set of edges Edge tmp = getMinCostEdge(); edge.add(tmp); p = tmp.start; q = tmp.end; minCost = cost[p][q]; //change the mark of every node for(int i = 0; i < n; i++){ if(cost[i][p] < cost[i][q]){ near[i] = p; }else{ near[i] = q; } } near[p] = near[q] = -1; } //to look for the smallest edge public Edge getMinCostEdge(){ Edge tmp = new Edge(); double min = INFINITY; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(cost[i][j] < min){ min = cost[i][j]; tmp.start = i; tmp.end = j; } } } return tmp; } //the main method of Prim public void prim(){ //to look for other n-2 edges for(int i = 2; i < n; i++){ double min = INFINITY; Edge tmp = new Edge(); for(int j = 0; j < n; j++){ if(near[j] != -1 && cost[j][near[j]] < min){ tmp.start = j; tmp.end = near[j]; min = cost[j][near[j]]; } } minCost += cost[tmp.start][tmp.end]; edge.add(tmp); near[tmp.start] = -1; for(int k = 0; k < n; k++){ if(near[k] != -1 && cost[k][near[k]] > cost[k][tmp.start]){ near[k] = tmp.start; } } } if(minCost >= INFINITY){ System.out.println("no spanning tree"); } } //to print out result public void print(){ System.out.println("--Prim's result--------------"); for(int i = 0; i < edge.size(); i++){ Edge e = edge.get(i); System.out.println("the " + (i+1) + "th edge:" + e.start + "" + e.end + " cost:" + cost[e.start][e.end]); } System.out.println("The minimum total cost is " + minCost); System.out.println("--End of Prim's--------------"); System.out.println('\n'); }} CLass Kruskal
package fwn.knzw.lab.classes;import java.util.ArrayList;import java.util.Scanner;public class Kruskal { private ArrayList edge = new ArrayList ();//to store all edges private ArrayList target = new ArrayList ();//to store the edges of MST private int[] parent ;//to mark which set a point belonging to private static double INFINITY = 99999999.99;//define an infinity private double minCost = 0.0;//the minimum cost private int n;//the number of nodes public Kruskal(){ init(); kruskal(); print(); } //to initiate the graph public void init(){ System.out.println("--MST Kruskal's alogrithm----"); Scanner scan = new Scanner(System.in); int p,q; double w; //input the number of nodes System.out.println("Input the number of nodes:"); n = scan.nextInt(); //build array 'parent' parent = new int[n]; //input the edges System.out.println("Input the graph(-1,-1,-1 to exit):"); while(true){ p = scan.nextInt(); q = scan.nextInt(); w = scan.nextDouble(); if(p < 0 || q < 0 || w < 0){ break; } Edge e = new Edge(); e.start = p; e.end = q; e.cost = w; edge.add(e); } minCost = 0.0; //mark all nodes with different numbers for(int i = 0; i < n; i++){ parent[i] = i; } } //to union the sets(join all nodes in j to k) public void union(int j, int k){ for(int i = 0; i < n; i++){ if(parent[i] == j){ parent[i] = k; } } } //the main method of Kruskal public void kruskal(){ //to find the smallest edge and move it from 'edge' to 'target' int i = 0; while(i < n-1 && edge.size() > 0){ double min = INFINITY; Edge minEdge = null; for(int j = 0; j < edge.size(); j++){ Edge tmp = edge.get(j); if(tmp.cost < min){ min = tmp.cost; minEdge = tmp; } } int jj = parent[minEdge.start]; int kk = parent[minEdge.end]; //only choose the edge which will not cause a ring if(jj != kk){ i++; target.add(minEdge); minCost += minEdge.cost; union(jj,kk); } edge.remove(minEdge); } if(i != n-1){ System.out.println("no spanning tree"); } } //to print out result public void print(){ System.out.println("--Kruskal's result-----------"); for(int i = 0; i < target.size(); ++i){ Edge e = target.get(i); System.out.println("the " + (i+1) + "th edge:" + e.start + "" + e.end + " cost:" + e.cost); } System.out.println("The minimum total cost is " + minCost); System.out.println("--End of Kruskal's-----------"); System.out.println('\n'); }}