Java最小生成树问题

Question

我正在研究实验室，如果可能，需要一些帮助。

我创建了一个多维数组，这个数组填充了大于等于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）其它两个类，但它们与这个特定问题无关。

我希望有人能够提供帮助，因为我花了数小时试图解决这个问题。

非常感谢。

米克

Answer 1

这里的问题是：

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方法来自你的main方法（）或方法，而不是来自类的顶层。
• 你也应该用方法初始化你的随机生成器
• 你不必用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(""); 
     } 
    } 
}