Java - Komponenten aus einem Graph berechnen / Algorithmus?

Hallo, ich arbeite gerade an einem Graphenprogramm und der nächste Schritt ist es ,mir die Zusammenhangskomponenten des Graphes auslesen zu lassen.

Eine dafür notwendige Wegmatrix habe ich schon programmiert:

public void berechneKomponenten()
    {
        
        for (int i = 0; i < Matrix.length; i++)
        {
            for(int j = 0; j < Matrix[i].length; j++)
            {
                if(WegMatrix[i][j] == 1)
                {
                    int buchstabe_int = i+65;
                    char buchstabe_char = (char) buchstabe_int;
                    
                    System.out.print(buchstabe_char + ",");
                }                        
            }        
        }
    }

Die Ausgabe sieht so aus:

A, A, A, B, B, C, C, C, D, D, D, E, E

--------------------------------------------------------

Und das ist im Prinzip auch richtig, denn:

Die Buchstaben (A-E) habe ich zum Verständnis hinzugefügt.
-------------------------------------------------------------------------------------

Meine Wegmatrix hat:

  • 3 A's
  • 2 B's
  • 3 C's
  • 3 D's
  • 2 E's

Verglichen mit meiner Ausgabe:

A, A, A => 3 A's
B, B => 2 B's
C, C, C => 3 C's
D, D, D = > 3 D's
E, E => 2 E's

-----------------------------------

Doch die Ausgabe sollte so aussehen: (Siehe K1 und K2)

bzw so:

Wie schaffe ich das?

Danke!

Bild zum Beitrag
Computer, programmieren, Java, Informatik
Java - Distanzmatrix Algorithmus, Wie ansetzen?

Hallo, ich bin gerade dabei ein Graphenprogramm zu schreiben und stecke bisschen bei der Distanzmatrix.

Ich weiß nicht ob sich jemand bei Graphentheorie auskennt oder nicht aber der Algorithmus für die Distanzmatrix ist relativ einfach. Nur das umsetzen in Code fällt mir sehr schwer und deswegen hoffe ich, dass ihr mir vielleicht dabei helfen könnt..

Der Algorithmus für eine Distanzmatrix lautet so:

Man hat eine Eingangsmatrix (Adjazentmatrix).
Die könnte so aussehen:

Man markiert sich alle Nuller die in der Adjazentmatrix vorkommen (AUßER DIE HAUPTDIAGONALE, DIE BLEIBT UNBERÜHRT).

Dann erstellt man sich eine eigene Matrix die man "DistanzMatrix" nennen kann und setzt alle Nuller die eben in der Adjazentmatrix vorkommen auf "Unendlich" oder auch auf INTEGER.MAX_VALUE in der Programmiersprache .

Das schaut dann so aus:

Also haben wir jetzt 2 Matrizen. Bis dahin habe ich es auch geschafft in meinem Programm. Die Ausgabe schaut bei mir so aus:

Die "-9" sind alle Nuller, die auf UNENDLICH gesetzt sind (siehe zweites Bild).

Der nächste Schritt ist es die Potenzen der Eingangsmatrix (Adjazentmatrix) zu berechnen. Das habe ich ebenfalls schon geschafft im Code.

Das heißt, die Adjazentmatrix (siehe Bild 1) wurde potenziert und so könnte das Ergebnis der Potenzberechnug aussehen.

Man schaut sich jetzt alle Nuller (außer die Hauptdiagonale von der Eingangsmatrix an (siehe Bild 1)) und markiert sich nur die Zahlen (rot), die sich von der Potenzierung der Eingangsmatrix verändert haben. (Außer die Nuller (=Neue Nuller die durch die Potenzierung entstanden sind bleiben auch weiterhin eine Null))

Und der letzte Schritt ist es jetzt, die von mir erstellte DistanzMatrix upzudaten, indem ich im ersten Schritt alle rote Zahlen von A²(G) in 2 umwandle. Alle Nuller die übrig bleiben, werden wieder in UNENDLICH umgewandelt.

Und das wird jetzt so oft wiederholt, bis es keine UNENDLICH Zeichen mehr in der Distanzmatrix gibt. Und aus UNENDLICH wird 3. Und immer so weiter.. Falls es zb nach der fünften Potenzierung immer noch Nuller bzw UNENDLICH Werte gibt dann wird aus UNENDLICH 5.

Somit ist D³(G) das Ergebnis.

Ich hoffe ich konnte es ausführlich genug erklären

Danke

Bild zum Beitrag
Computer, Schule, Technik, programmieren, Java, Informatik, Technologie, Algorithmus, Graphentheorie
Weitere Inhalte können nur Nutzer sehen, die bei uns eingeloggt sind.