Алгоритм Крускала с матричным массивом смежности indexoutofboundsexception = -1 - PullRequest
Новая
       39

Алгоритм Крускала с матричным массивом смежности indexoutofboundsexception = -1

0 голосов
/ 27 октября 2019

Я пытаюсь написать программу, которая принимает матрицу смежности, целые числа представляют вес ребра от вершины к вершине. И затем делает минимальное остовное дерево, используя алгоритм Крускала. Проблема, с которой я сталкиваюсь, заключается в том, что я выполняю свой код и получаю индекс массива за пределами исключения. Исключение в потоке "main" java.lang.ArrayIndexOutOfBoundsException: -1

Я думаю, что проблема в том, когда я установил свой мин в моем методе kruskalMST. Я не знаю, как установить a и b равными. Я пробовал 0 для обоих, и это только продолжало цикл и цикл, и у меня есть их в -1 прямо сейчас, и это только дает мне эту ошибку. если кто-то знает, как это исправить, это было бы здорово. правильный вывод должен быть:

1 -> 3 вес: 1

0 -> 3 вес: 2

1 -> 2 вес: 3

1 -> 4 вес: 5 

public class Main {
static int V = 5;
static int[] parent = new int[V];
public static void main(String[] args) {
    int cost[][] = {
            {0, 4, 0, 2, 0},
            {4, 0, 3, 1, 5},
            {0, 3, 0, 0, 6},
            {2, 1, 0, 0, 7},
            {0, 5, 6, 7, 0},
    };
    // Print the solution
    kruskalMST(cost);
}
// Find set of vertex i
public static int find(int i) {
    while (parent[i] != i)
        i = parent[i];
    return i;
}
// Does union of i and j. It returns
// false if i and j are already in same
// set.
public static void union(int i, int j) {
    int a = find(i);
    int b = find(j);
    parent[a] = b;
}
// Finds MST using Kruskal's algorithm
public static void kruskalMST(int cost[][]) {
    // Initialize sets of disjoint sets.
    for (int i = 0; i < V; i++)
        parent[i] = i;
    // Include minimum weight edges one by one
    int edge_count = 0;
    while (edge_count < V - 1) {
        int min = 0, a = -1, b = -1;
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (find(i) != find(j) && cost[i][j] < min) {
                    min = cost[i][j];
                    a = i;
                    b = j;
                }
            }
        }
        union(a, b);
        System.out.printf(a + " --> " + b + " weight: " + min + "\n");
    }
}
...