java - 在 Java 中实现 Kruskal 的最小生成树时出错

Question

我尝试用 Java 实现 Kruskal 的最小生成树。我正在使用 Eclipse 进行写作。 我使用此网站( https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/ )开始并使用德语命令和我自己的更大示例更改了代码。

这是我的代码:

package Kruskal_Algorithmus;

//Java-Programm für den Kruskal Algorithmus
//Ziel ist es einen minimalen Spannbaum aus einem gegebenen zusammenhängenden, ungerichteten, endlichen
//und kantengewichteten Graphen zu erzeugen.

import java.util.*; 
import java.lang.*; 
import java.io.*; 

class Graph 
{ 
    // Erstellung einer Klasse zur Erzeugung einer neuen Kante im Graphen 
    class Kante implements Comparable<Kante> 
    { 
        int quelle, richtung, gewicht; 

        // Erzeugung einer Vergleichs-Funktion damit eine Sortierung der gegeben Kanten
        // nach ihrem Gewicht / Kosten möglich ist
        public int compareTo(Kante kantenVergleich) 
        { 
            return this.gewicht-kantenVergleich.gewicht; 
        } 
    }; 


    // Erstellung einer Klasse um Teilmenge mit Hilfe von Union-Find zu finden
    class subset 
    { 
        int parent, rank; 
    }; 



    int K, E; // K => Anzahl der Knoten & E => Anzahl der Kanten 
    Kante kante[]; // Zusammenfassung aller Kanten im Kanten-Array 

    // Graph mit K Knoten und E (edge) Kanten wird erstellt
    Graph(int k, int e) 
    { 
        K = k; 
        E = e; 
        kante = new Kante[E]; 
        for (int i=0; i<e; ++i) 
            kante[i] = new Kante(); 
    } 

    // Erstellung einer Funktion die eine gewünschte Teilmenge aus den Elemente i heraus sucht
    // (Anwendung von "Path compression")
    int find(subset teilmengen[], int i) 
    { 
        // Suche und vergabe der Eltern-Teilmenge (parent) 
        if (teilmengen[i].parent != i) 
            teilmengen[i].parent = find(teilmengen, teilmengen[i].parent); 

        return teilmengen[i].parent; 
    } 

    // Eine Funktion die die Teilmengen x und y vereint und das Array subsets bildet
    void Union(subset subsets[], int x, int y) 
    { 
        int xroot = find(subsets, x); 
        int yroot = find(subsets, y); 

        // Teilbäume werden nach ihrem Rang in der Sortierung geordnet
        if (subsets[xroot].rank < subsets[yroot].rank) 
            subsets[xroot].parent = yroot; 
        else if (subsets[xroot].rank > subsets[yroot].rank) 
            subsets[yroot].parent = xroot; 

        // Falls zwei Mal der selbe Rang auftaucht wird ein Element einen Rang weiter nach unten geschoben
        else
        { 
            subsets[yroot].parent = xroot; 
            subsets[xroot].rank++; 
        } 
    } 

    // Funktion zur Erstellung des Minimal Spanning Tree nach Kruskal
    void KruskalMST() 
    { 
        Kante ergebnis[] = new Kante[K]; // hier wird finaler MST gespeichert
        int e = 0; // Index-Variable, welche für das Ergebnis-Array benötigt wird 
        int i = 0; // Index-Variable welche für die sortierten Kanten benötigt wird
        for (i=0; i<K; ++i) 
            ergebnis[i] = new Kante(); 

        // Schritt 1: Alle Kanten werden in nicht absteigender Reihenfolge nach ihrem 
        // Gewicht / ihren Kosten sortiert.
        // Da gegebener Graph ggf. nicht zu ändern ist, erstellen wir eine Kopie
        // des Kanten-Arrays.
        Arrays.sort(kante); 

        // Zuweisung, unter welchem Array die zu erzeugenden Teilmengen gespeichert werden
        subset subsets[] = new subset[K]; 
        for(i=0; i<K; ++i) 
            subsets[i]=new subset(); 

        // Teilmengen mit einzelnen Elementen werden erzeugt
        for (int v = 0; v < K; ++v) 
        { 
            subsets[v].parent = v; 
            subsets[v].rank = 0; 
        } 

        i = 0; // Index-Variable, welche die nächste zubearbeitende Kante auswählt 

        // Ziel: Kantenmenge des MSP = Knotenanzahl - 1 
        while (e < K - 1) 
        { 
            // Schritt 2: Kante mit geringsten Kosten wird ausgewählt.
            // Index-Variable wird für nächste Wiederholung um 1 erhöht.
            Kante next_edge = new Kante(); 
            next_edge = kante[i++]; 

            int x = find(subsets, next_edge.quelle); 
            int y = find(subsets, next_edge.richtung); 

            // Wenn das hinzufügen der Kante in den MST keinen Kreis / Zyklus ergibt,
            // wird Kante zur Lösung hinzugefügt und Variable des Lösungs-Index um 1 erhöht.

            if (x != y) 
            { 
                ergebnis[e++] = next_edge; 
                Union(subsets, x, y); 
            } 
            // Falls es doch zu einem Kreis kommt, wird die ausgewählte Kante verworfen.
        } 

        // Ergebnisse werden mithilfe des Ergebnis-Arrays auf der Konsole ausgegeben.
        // Der fertige MST ist erkennbar. 
        System.out.println("Der gesuchte Minimal Spanning Tree wird folgendermaßen aufgebaut:"); 
        for (i = 0; i < e; ++i) 
            System.out.println(ergebnis[i].quelle+" -> " + 
                ergebnis[i].richtung+" Gewicht: " + ergebnis[i].gewicht); 
    } 

    // ausführbares Programm: 
    public static void main (String[] args) 
    { 

        //gegebener Graph wird im Programm erstellt:

        int knotenAnzahl = 12; // Anzahl der Knoten im gegebenen Graphen 
        int kantenAnzahl = 66; // Anzahl der Kanten im gegebenen Graphen
        Graph graph = new Graph(knotenAnzahl, kantenAnzahl); 

        // Kante 1 -> 2
        graph.kante[0].quelle = 1; 
        graph.kante[0].richtung = 2; 
        graph.kante[0].gewicht = 32; 

        // Kante 1 -> 3 
        graph.kante[1].quelle = 1; 
        graph.kante[1].richtung = 3; 
        graph.kante[1].gewicht = 45; 

        // Kante 1 -> 4
        graph.kante[2].quelle = 1; 
        graph.kante[2].richtung = 4; 
        graph.kante[2].gewicht = 43; 

        // Kante 1 -> 5 
        graph.kante[3].quelle = 1; 
        graph.kante[3].richtung = 5; 
        graph.kante[3].gewicht = 28; 

        // Kante 1 -> 6 
        graph.kante[4].quelle = 1; 
        graph.kante[4].richtung = 6; 
        graph.kante[4].gewicht = 11; 

        // Kante 1 -> 7 
        graph.kante[5].quelle = 1; 
        graph.kante[5].richtung = 7; 
        graph.kante[5].gewicht = 16;

        // Kante 1 -> 8 
        graph.kante[6].quelle = 1; 
        graph.kante[6].richtung = 8; 
        graph.kante[6].gewicht = 28;    

        // Kante 1 -> 9 
        graph.kante[7].quelle = 1; 
        graph.kante[7].richtung = 9; 
        graph.kante[7].gewicht = 37;

        // Kante 1 -> 10 
        graph.kante[8].quelle = 1; 
        graph.kante[8].richtung = 10; 
        graph.kante[8].gewicht = 46;

        // Kante 1 -> 11
        graph.kante[9].quelle = 1; 
        graph.kante[9].richtung = 11; 
        graph.kante[9].gewicht = 8;

        // Kante 1 -> 12 
        graph.kante[10].quelle = 1; 
        graph.kante[10].richtung = 12; 
        graph.kante[10].gewicht = 5;

        // Kante 2 -> 3
        graph.kante[11].quelle = 2; 
        graph.kante[11].richtung = 3; 
        graph.kante[11].gewicht = 12;

        // Kante 2 -> 4
        graph.kante[12].quelle = 2; 
        graph.kante[12].richtung = 4; 
        graph.kante[12].gewicht = 16;

        // Kante 2 -> 5 
        graph.kante[13].quelle = 2; 
        graph.kante[13].richtung = 5; 
        graph.kante[13].gewicht = 42;

        // Kante 2 -> 6 
        graph.kante[14].quelle = 2; 
        graph.kante[14].richtung = 6; 
        graph.kante[14].gewicht = 36;

        // Kante 2 -> 7
        graph.kante[15].quelle = 2; 
        graph.kante[15].richtung = 7; 
        graph.kante[15].gewicht = 22;

        // Kante 2 -> 8
        graph.kante[16].quelle = 2; 
        graph.kante[16].richtung = 8; 
        graph.kante[16].gewicht = 17;

        // Kante 2 -> 9
        graph.kante[17].quelle = 2; 
        graph.kante[17].richtung = 9; 
        graph.kante[17].gewicht = 50;

        // Kante 2 -> 10
        graph.kante[18].quelle = 2; 
        graph.kante[18].richtung = 10; 
        graph.kante[18].gewicht = 33;

        // Kante 2 -> 11
        graph.kante[19].quelle = 2; 
        graph.kante[19].richtung = 11; 
        graph.kante[19].gewicht = 8;

        // Kante 2 -> 12
        graph.kante[20].quelle = 2; 
        graph.kante[20].richtung = 12; 
        graph.kante[20].gewicht = 2;

        // Kante 3 -> 4
        graph.kante[21].quelle = 3; 
        graph.kante[21].richtung = 4; 
        graph.kante[21].gewicht = 41;

        // Kante 3 -> 5
        graph.kante[22].quelle = 3; 
        graph.kante[22].richtung = 5; 
        graph.kante[22].gewicht = 34;

        // Kante 3 -> 6
        graph.kante[23].quelle = 3; 
        graph.kante[23].richtung =6; 
        graph.kante[23].gewicht = 47;

        // Kante 3 -> 7
        graph.kante[24].quelle = 3; 
        graph.kante[24].richtung = 7; 
        graph.kante[24].gewicht = 49;

        // Kante 3 -> 8
        graph.kante[25].quelle = 3; 
        graph.kante[25].richtung = 8; 
        graph.kante[25].gewicht = 46;

        // Kante 3 -> 9
        graph.kante[26].quelle = 3; 
        graph.kante[26].richtung = 9; 
        graph.kante[26].gewicht = 36;

        // Kante 3 -> 10
        graph.kante[27].quelle = 3; 
        graph.kante[27].richtung = 10; 
        graph.kante[27].gewicht = 49;

        // Kante 3 -> 11
        graph.kante[28].quelle = 3; 
        graph.kante[28].richtung = 11; 
        graph.kante[28].gewicht = 32;

        // Kante 3 -> 12
        graph.kante[29].quelle = 3; 
        graph.kante[29].richtung = 12; 
        graph.kante[29].gewicht = 35;

        // Kante 4 -> 5
        graph.kante[30].quelle = 4; 
        graph.kante[30].richtung = 5; 
        graph.kante[30].gewicht = 35;

        // Kante 4 -> 6
        graph.kante[31].quelle = 4; 
        graph.kante[31].richtung = 6; 
        graph.kante[31].gewicht = 42;

        // Kante 4 -> 7
        graph.kante[32].quelle = 4; 
        graph.kante[32].richtung = 7; 
        graph.kante[32].gewicht = 2;

        // Kante 4 -> 8
        graph.kante[33].quelle = 4; 
        graph.kante[33].richtung = 8; 
        graph.kante[33].gewicht = 2;

        // Kante 4 -> 9
        graph.kante[34].quelle = 4; 
        graph.kante[34].richtung = 9; 
        graph.kante[34].gewicht = 12;

        // Kante 4 -> 10
        graph.kante[35].quelle = 4; 
        graph.kante[35].richtung = 10; 
        graph.kante[35].gewicht = 47;

        // Kante 4 -> 11
        graph.kante[36].quelle = 4; 
        graph.kante[36].richtung = 11; 
        graph.kante[36].gewicht = 39;

        // Kante 4 -> 12
        graph.kante[37].quelle = 4; 
        graph.kante[37].richtung = 12; 
        graph.kante[37].gewicht = 15;

        // Kante 5 -> 6
        graph.kante[38].quelle = 5; 
        graph.kante[38].richtung = 6; 
        graph.kante[38].gewicht = 19;

        // Kante 5 -> 7
        graph.kante[39].quelle = 5; 
        graph.kante[39].richtung = 7; 
        graph.kante[39].gewicht = 20;

        // Kante 5 -> 8
        graph.kante[40].quelle = 5; 
        graph.kante[40].richtung = 8; 
        graph.kante[40].gewicht = 5;

        // Kante 5 -> 9
        graph.kante[41].quelle = 5; 
        graph.kante[41].richtung = 9; 
        graph.kante[41].gewicht = 23;

        // Kante 5 -> 10
        graph.kante[42].quelle = 5; 
        graph.kante[42].richtung = 10; 
        graph.kante[42].gewicht = 14;

        // Kante 5 -> 11
        graph.kante[43].quelle = 5; 
        graph.kante[43].richtung = 11; 
        graph.kante[43].gewicht = 9;

        // Kante 5 -> 12
        graph.kante[44].quelle = 5; 
        graph.kante[44].richtung = 12; 
        graph.kante[44].gewicht = 47;

        // Kante 6 -> 7
        graph.kante[45].quelle = 6; 
        graph.kante[45].richtung = 7; 
        graph.kante[45].gewicht = 43;

        // Kante 6 -> 8
        graph.kante[46].quelle = 6; 
        graph.kante[46].richtung = 8; 
        graph.kante[46].gewicht = 6;

        // Kante 6 -> 9
        graph.kante[47].quelle = 6; 
        graph.kante[47].richtung = 9; 
        graph.kante[47].gewicht = 24;

        // Kante 6 -> 10
        graph.kante[48].quelle = 6; 
        graph.kante[48].richtung = 10; 
        graph.kante[48].gewicht = 32;

        // Kante 6 -> 11
        graph.kante[49].quelle = 6; 
        graph.kante[49].richtung = 11; 
        graph.kante[49].gewicht = 44;

        // Kante 6 -> 12
        graph.kante[50].quelle = 6; 
        graph.kante[50].richtung = 12; 
        graph.kante[50].gewicht = 3;

        // Kante 7 -> 8
        graph.kante[51].quelle = 7; 
        graph.kante[51].richtung = 8; 
        graph.kante[51].gewicht = 14;

        // Kante 7 -> 9
        graph.kante[52].quelle = 7; 
        graph.kante[52].richtung = 9; 
        graph.kante[52].gewicht = 26;

        // Kante 7 -> 10
        graph.kante[53].quelle = 7; 
        graph.kante[53].richtung = 10; 
        graph.kante[53].gewicht = 39;

        // Kante 7 -> 11
        graph.kante[54].quelle = 7; 
        graph.kante[54].richtung = 11; 
        graph.kante[54].gewicht = 8;

        // Kante 7 -> 12
        graph.kante[55].quelle = 7; 
        graph.kante[55].richtung = 12; 
        graph.kante[55].gewicht = 24;

        // Kante 8 -> 9
        graph.kante[56].quelle = 8; 
        graph.kante[56].richtung = 9; 
        graph.kante[56].gewicht = 1;

        // Kante 8 -> 10
        graph.kante[57].quelle = 8; 
        graph.kante[57].richtung = 10; 
        graph.kante[57].gewicht = 19;

        // Kante 8 -> 11
        graph.kante[58].quelle = 8; 
        graph.kante[58].richtung = 11; 
        graph.kante[58].gewicht = 14;

        // Kante 8 -> 12
        graph.kante[59].quelle = 8; 
        graph.kante[59].richtung = 12; 
        graph.kante[59].gewicht = 39;

        // Kante 9 -> 10
        graph.kante[60].quelle = 9; 
        graph.kante[60].richtung = 10; 
        graph.kante[60].gewicht = 6;

        // Kante 9 -> 11
        graph.kante[61].quelle = 9; 
        graph.kante[61].richtung = 11; 
        graph.kante[61].gewicht = 47;

        // Kante 9 -> 12
        graph.kante[62].quelle = 9; 
        graph.kante[62].richtung = 12; 
        graph.kante[62].gewicht = 25;

        // Kante 10 -> 11
        graph.kante[63].quelle = 10; 
        graph.kante[63].richtung = 11; 
        graph.kante[63].gewicht = 15;

        // Kante 10 -> 12
        graph.kante[64].quelle = 10; 
        graph.kante[64].richtung = 12; 
        graph.kante[64].gewicht = 21;

        // Kante 11 -> 12
        graph.kante[65].quelle = 11; 
        graph.kante[65].richtung = 12; 
        graph.kante[65].gewicht = 11;


        graph.KruskalMST(); 
    } 
} 

在 Eclipse 中我收到此错误代码:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 12 out of bounds for length 12
    at Kruskal_Algorithmus.Graph.find(Graph.java:53)
    at Kruskal_Algorithmus.Graph.KruskalMST(Graph.java:117)
    at Kruskal_Algorithmus.Graph.main(Graph.java:479)

我对 Java 编码非常陌生，不知道如何让这个程序运行。希望您能给我一些建议。

谢谢!

Answer 1

您的图形节点编号似乎从 1 开始:1, 2, 3, ..., 12

Java 中的数组索引以 0 开头。当您创建一个包含 12 个项目的数组时，最后一个项目的索引为 11。索引 12 处没有数组元素。

您有几个选择:您可以更改编号，以便节点编号与数组索引匹配。这可能是最简单的。例如，边 6-12 变为边 5-11。

    // Kante 6 -> 12
    graph.kante[50].quelle = 5; 
    graph.kante[50].richtung = 11;

或者，从节点号中减去 1 以获取循环中的索引。或者向由图节点索引的所有数组添加额外的空间。例如:

    subset subsets[] = new subset[K + 1];

如果您选择最后一个选项，您还必须更改在节点上迭代的所有循环。当您的节点编号为 1-12 时，当前在 0-11 上迭代。

    for(i=1; i<=K; ++i) 
        subsets[i]=new subset();