java讲解、讲解java程序设计、讲解java PrimVsKruskal 程序
- 首页 >> C/C++编程*/
import java.util.Scanner;
import java.io.File;
//Do not change the name of the PrimVsKruskal class
public class PrimVsKruskal{
/* PrimVsKruskal(G)
Given an adjacency matrix for connected graph G, with no self-loops or parallel edges,
determine if the minimum spanning tree of G found by Prim's algorithm is equal to
the minimum spanning tree of G found by Kruskal's algorithm.
If G[i][j] == 0.0, there is no edge between vertex i and vertex j
If G[i][j] > 0.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 boolean PrimVsKruskal(double[][] G){
int n = G.length;
/* Build the MST by Prim's and the MST by Kruskal's */
/* (You may add extra methods if necessary) */
/* ... Your code here ... */
/* Determine if the MST by Prim equals the MST by Kruskal */
boolean pvk = true;
/* ... Your code here ... */
return pvk;
}
/* main()
Contains code to test the PrimVsKruskal 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\n",args[0]);
return;
}
System.out.printf("Reading input values from %s.\n",args[0]);
}else{
s = new Scanner(System.in);
System.out.printf("Reading input values from stdin.\n");
}
int n = s.nextInt();
double[][] G = new double[n][n];
int valuesRead = 0;
for (int i = 0; i < n && s.hasNextDouble(); i++){
for (int j = 0; j < n && s.hasNextDouble(); j++){
G[i][j] = s.nextDouble();
if (i == j && G[i][j] != 0.0) {
System.out.printf("Adjacency matrix contains self-loops.\n");
return;
}
if (G[i][j] < 0.0) {
System.out.printf("Adjacency matrix contains negative values.\n");
return;
}
if (j < i && G[i][j] != G[j][i]) {
System.out.printf("Adjacency matrix is not symmetric.\n");
return;
}
valuesRead++;
}
}
if (valuesRead < n*n){
System.out.printf("Adjacency matrix for the graph contains too few values.\n");
return;
}
boolean pvk = PrimVsKruskal(G);
System.out.printf("Does Prim MST = Kruskal MST? %b\n", pvk);
}
}