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(""); 
     } 
    } 
}