我正在实验室工作，如果可能的话需要一些帮助。
我创建了一个多维数组，其中填充了大于等于 0 到 100(含)的随机整数，并且我尝试将 Prim 的算法(通过我在另一个类中拥有的方法)应用到这个多维数组，但是它不断给我带来不需要的结果(要么是零，要么是我为“n”输入的值)。
请注意，我已将 Prim 的算法(通过另一个类中的方法)应用于另外两个数组，并且效果非常好；然而，既然我已经创建了一个完全由 0 到 100 之间的随机自然整数填充的多维数组，它就不再工作了。这是类中的代码(我已将代码保留在我所处理的上述两个数组中，以防可以从中派生出某些内容):
import java.util.Arrays;
import java.util.Random;
public class Lab6 {
static double[][] g = new double[][] {{0, 1, 2} , {1, 0, 3} , {2, 3, 0}};
static double mst[][] = MST.PrimsMST(g);
static double[][] lecExample = new double[][] {{0, 1, 2, 3, 0} , {1, 0, 6, 0, 5} , {2, 6, 0 ,4, 1} , {3, 0, 4, 0, 2} , {0, 5, 1, 2, 0}};
static double mst2[][] = MST.PrimsMST(lecExample);
public static void printArray(){
System.out.println("Matrix (g):");
for (int i = 0; i < g.length; i++) {
for (int c = 0; c < g[i].length; c++) {
System.out.print(" " + g[i][c]);
}
System.out.println("");
}
System.out.println();
System.out.println("MST:");
for (int i = 0; i < mst.length; i++){
for (int c = 0; c < mst[i].length; c++){
System.out.print(" " + mst[i][c]);
}
System.out.println("");
}
System.out.println("Matrix (lecExample):");
for (int i = 0; i < lecExample.length; i++) {
for (int c = 0; c < lecExample[i].length; c++) {
System.out.print(" " + lecExample[i][c]);
}
System.out.println("");
}
System.out.println();
System.out.println("MST2:");
for (int i = 0; i < mst2.length; i++){
for (int c = 0; c < mst2[i].length; c++){
System.out.print(" " + mst2[i][c]);
}
System.out.println("");
}
}
static Random random = new Random();
static int r = random.nextInt() & 100;
public static void randomArray(int n){
double[][] array = new double[][] {{n, n, n, n, n}, {n, n, n, n, n}, {n, n, n, n, n}, {n, n, n, n, n}, {n, n, n, n, n}};
double mst3[][] = MST.PrimsMST(array);
System.out.println("Matrix (Random Number Array):");
for(int i = 0 ; i < array.length ; i++ ) {
for (int c = 0 ; c < array[i].length; c++ ) {
array[i][c] = random.nextInt(101);
}
}
for(double[] a: array) {
System.out.println(Arrays.toString(a));
}
System.out.println("MST3:");
for (int i = 0; i < mst3.length; i++){
for (int c = 0; c < mst3[i].length; c++){
System.out.print(" " + mst3[i][c]);
}
System.out.println("");
}
}
public static void main(String[] args){
printArray();
System.out.println("\n");
randomArray(50);
}
}
MST.java:
import java.util.*;
public class MST
{
//Search for the next applicable edge
static private Edge LocateEdge(ArrayList<Integer> v,ArrayList<Edge> edges)
{
for (Iterator<Edge> it = edges.iterator(); it.hasNext();)
{
Edge e = it.next();
int x = e.i;
int y = e.j;
int xv = v.indexOf(x);
int yv = v.indexOf(y);
if (xv > -1 && yv == -1)
{
return(e);
}
if (xv == -1 && yv > -1)
{
return(e);
}
}
//Error condition
return(new Edge(-1,-1,0.0));
}
@SuppressWarnings("unchecked")
//d is a distance matrix, high value edges are more costly
//Assume that d is symmetric and square
public static double[][] PrimsMST(double[][] d)
{
int i,j,n = d.length;
double res[][] = new double[n][n];
//Store edges as an ArrayList
ArrayList<Edge> edges = new ArrayList<Edge>();
for(i=0;i<n-1;++i)
{
for(j=i+1;j<n;++j)
{
//Only non zero edges
if (d[i][j] != 0.0) edges.add(new Edge(i,j,d[i][j]));
}
}
//Sort the edges by weight
Collections.sort(edges,new CompareEdge());
//Don't do anything more if all the edges are zero
if (edges.size() == 0) return(res);
//List of variables that have been allocated
ArrayList<Integer> v = new ArrayList<Integer>();
//Pick cheapest edge
v.add(edges.get(0).i);
//Loop while there are still nodes to connect
while(v.size() != n)
{
Edge e = LocateEdge(v,edges);
if (v.indexOf(e.i) == -1) v.add(e.i);
if (v.indexOf(e.j) == -1) v.add(e.j);
res[e.i][e.j] = e.w;
res[e.j][e.i] = e.w;
}
return(res);
}
}
每当我运行该程序时，结果都是这样:
Matrix (Random Number Array):
[85.0, 11.0, 79.0, 25.0, 30.0]
[62.0, 55.0, 39.0, 21.0, 92.0]
[31.0, 76.0, 3.0, 74.0, 43.0]
[59.0, 97.0, 91.0, 60.0, 7.0]
[96.0, 44.0, 26.0, 66.0, 31.0]
MST3:
0.0 50.0 50.0 50.0 50.0
50.0 0.0 0.0 0.0 0.0
50.0 0.0 0.0 0.0 0.0
50.0 0.0 0.0 0.0 0.0
50.0 0.0 0.0 0.0 0.0
还有另外两个类处理存储边权重 (Edge.java) 并比较边权重 (CompareEdges.java)，但它们与这个特定问题无关。
我希望有人能够提供帮助，因为我花了几个小时试图解决这个问题。
非常感谢。
米克
最佳答案
问题是这样的:
public static void randomArray(int n){
n = 0;
double[][] array = new double[][] {{n, n, n, n, n}, {n, n, n, n, n}, {n, n, n, n, n}, {n, n, n, n, n}, {n, n, n, n, n}};
double mst3[][] = MST.PrimsMST(array);
您创建一个由 0 组成的数组，然后对其应用 MST。然后用随机数覆盖数组，但 MST 方法是在 0 数组上调用的，而不是在随机数数组上调用的。
另外，在设计层面上，我认为你应该花一些时间来重构和分解你的代码，否则在构建更复杂的项目时你会遇到很多问题:
- 您应该从主方法 () 或方法中调用 MST 方法，而不是从类的顶层调用。
- 您还应该在方法中初始化随机生成器
- 您不必用 0 来初始化数组，只需指定大小即可。 (仅当您想使用特定值初始化数组时才应使用 = {} 初始化)
- 您编写了 5 次数组显示代码，完全相同，这表明您应该有一个方法来执行此操作。
- 此外，您使用
double数组来存储int，所以我认为您可能想切换到int
所以我认为你的类应该看起来更像这样。
public class Lab6{
static int[][] g= new int[][] {{0, 1, 2} , {1, 0, 3} , {2, 3, 0}};
static int[][] lecExample = new int[][] {{0, 1, 2, 3, 0} , {1, 0, 6, 0, 5} , {2, 6, 0 ,4, 1} , {3, 0, 4, 0, 2} , {0, 5, 1, 2, 0}};
public static void main(String[] args){
displayArray(g);
displayArray(MST.PrimMST(g));
displayArray(lecExample);
displayArray(MST.PrimMST(lecExample));
int[][] randomArray = getRandomArray(50);
displayArray(randomArray);
displayArray(MST.PrimMST(randomArray));
}
public static int[][] getRandomArray(int n){
int[][] a = new int[n][n];
Random r = new Random();
for(int i = 0; i < a.length; i++){
for(int j = 0; j < a[i].length; j++){
a[i][j] = r.nextInt();
}
}
return a;
}
public static void displayArray(int[] a){
for(int i = 0; i < a.length; i++){
for(int j = 0; j < a[i].length; j++){
System.out.print(" " + a[i][j]);
}
System.out.println("");
}
}
}
关于Java最小生成树问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5245341/