Я работаю в лаборатории и, если возможно, нуждаюсь в помощи.
Я создал многомерный массив, который заполняется случайными целыми числами> = 0 до 100 (включительно), и я пытаюсь применить Prim'sАлгоритм (через метод, который у меня есть в другом классе) для этого многомерного массива, но он продолжает давать мне нежелательные результаты (либо нули, либо значение, которое я ввел для 'n').
Обратите вниманиечто я применил алгоритм Прима (с помощью метода из другого класса) к двум другим массивам, и он отлично работал;однако теперь, когда я создал многомерный массив, полностью заполненный случайными натуральными числами от 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), но они не имеют отношения к этому конкретному вопросу.
Я надеюсь, что кто-то сможет помочь, поскольку я потратил несколько часов, пытаясь решить эту проблему.
Большое спасибо.
Мик