Methoden Implementieren von Knotengrad - 2 Methoden Matrix und Liste

[Terence86]

Hi Leute ich soll 2 Methoden schreiben die als Eingabe eine Adjazenzmatrix (int[][]) oder Adjazenzliste (int[][]) benutzen.
Die erste Methode habe ich mit einem Freund zusammen gemacht, gehe mal davon aus das die stimmt (der kennt sich ganz gut aus), zweite Methode habe ich "übertragen" stimmt aber sicher nicht da Matrix&Liste nicht dasselbe sind. Fragen zu Punkte im Code habe ich darunter mit // Kommentar gekennzeichnet. Habe leider mit Arrays noch nie programmiert vielleicht als Hinweis.

import java.util.*;

public class Name {


    public static class Degree{
        public int[] vertexDegrees; //gibt fur alle Knoten i 2 (0; 1; :::; n 1) am Index i den entsprechenden Knotengrad an
        public int smallDelta;
        public int bigDelta;
    }
/**
*This method takes an adjacency matrix of a graph, calculates the degree of every vertex, its big and small delta
*and returns a Degree-Object containing all this values.
**/
public static Delivery.Degree getDegreesFromAdjMatrix(int[][] adjMatrix){
    Degree result = new Degree();
    result.smallDelta = Integer.MAX_VALUE;
    result.bigDelta = 0;
    for(int i = 0 ; i < adjMatrix.length - 1; i++) {
        // Was passiert hier? Geht der hier die Zeile durch oder sie Spalte, Komplett oder nur einzelne Werte?
      
        for(int j = 0 ;  j < adjMatrix[0].length - 1; j++){
        // Selbe Frage wie oben.   
            if(i == j){
                result.vertexDegrees[i] = result.vertexDegrees[i]  + adjMatrix[i][j] * 2;
                // Das war glaub ich weil Schleifen doppelt gezählt werden, aber wie sieht es in der Liste aus?
            } else {
                result.vertexDegrees[i] = result.vertexDegrees[i]  + adjMatrix[i][j];
            }
        }
      
        if(result.smallDelta > result.vertexDegrees[i] ){
            result.smallDelta = result.vertexDegrees[i];
        }
        if(result.bigDelta < result.vertexDegrees[i]){
            result.bigDelta = result.vertexDegrees[i];
            //Beides mal die Ausgabe ist verständlich
        }
      
    }
    return result;
}
/**
*This method takes an adjacency list of a graph, calculates the degree of every vertex, its big and small delta
*and returns a Degree-Object containing all this values.
**/
public static Delivery.Degree getDegreesFromAdjList(int[][] adjList){
    Degree result = new Degree();
    result.smallDelta = Integer.MAX_VALUE;
    result.bigDelta = 0;
  
    for(int i = 0 ; i < adjList.length - 1; i++) {
      
        for(int j = 0 ; j < adjList.length -1; j++) {
          
            if(i==j) {
                result.vertexDegrees[i] = result.vertexDegrees[i] + adjList[i][j] *2;
            } else {
                result.vertexDegrees[i] = result.vertexDegrees[i] + adjList[i][j];
              
                // Idee ist ja das man bei der Liste den Knotengrad durch die Länge der Liste bekommt ->größter ist Max und kleinster ist Min.
            }
              
            }
      
        if(result.smallDelta > result.vertexDegrees[i]) {
            result.smallDelta = result.vertexDegrees[i];
        }
        if(result.bigDelta > result.vertexDegrees[i]) {
            result.bigDelta = result.vertexDegrees[i];
          
        }
      
      
    }
  
    return result;
}

}

 

[Meniskusschaden]

Hi Leute ich soll 2 Methoden schreiben die als Eingabe eine Adjazenzmatrix (int[][]) oder Adjazenzliste (int[][]) benutzen.

Ist das ein Tippfehler oder soll auch die Adjazenzliste als 2D-Array abgebildet werden? Ich gehe jetzt davon aus, dass Letzteres zutrifft und dass

adjList[i]

ein Array mit den Nummern der Nachbarknoten des Knotens i enthält. Falls das nicht stimmen sollte, wäre mein Antwortteil zur Adjazenzliste hinfällig.

for(int i = 0 ; i < adjMatrix.length - 1; i++) {
        // Was passiert hier? Geht der hier die Zeile durch oder sie Spalte, Komplett oder nur einzelne Werte?

Üblicherweise repräsentiert der erste Index die Zeile und der zweite die Spalte. Also: Zeile.
Ich gehe aber davon aus, dass es hier um ungerichtete Graphen ohne Kantengewichte geht (sonst wäre dein Algorithmus fehlerhaft) und da ist es ohnehin egal, weil die Matrix symmetrisch zur Diagonalen ist.
Was du mit "Komplett oder nur einzelne Werte" meinst, ist mir nicht klar. Diese Schleife wird für jede Zeile einmal durchlaufen.

for(int j = 0 ;  j < adjMatrix[0].length - 1; j++){
        // Selbe Frage wie oben.

Siehe vorige Antwort. Es wäre aber korrekter, in der Schleifenbedingung nicht die Länge von Zeile 0, sondern von Zeile i zu prüfen.

result.vertexDegrees[i] = result.vertexDegrees[i]  + adjMatrix[i][j] * 2;
                // Das war glaub ich weil Schleifen doppelt gezählt werden, aber wie sieht es in der Liste aus?

Ja.

        if(result.smallDelta > result.vertexDegrees[i] ){
            result.smallDelta = result.vertexDegrees[i];
        }
        if(result.bigDelta < result.vertexDegrees[i]){
            result.bigDelta = result.vertexDegrees[i];
            //Beides mal die Ausgabe ist verständlich
        }

Ja, ist beide Male verständlich.

       for(int j = 0 ; j < adjList.length -1; j++) {
       
            if(i==j) {
                result.vertexDegrees[i] = result.vertexDegrees[i] + adjList[i][j] *2;
            } else {
                result.vertexDegrees[i] = result.vertexDegrees[i] + adjList[i][j];
           
                // Idee ist ja das man bei der Liste den Knotengrad durch die Länge der Liste bekommt ->größter ist Max und kleinster ist Min.
            }
           
            }

Man könnte die Listenlänge als Knotengrad verwenden, wenn da nicht der Sonderfall des mit sich selbst benachbarten Knotens wäre. Deine Prüfung, ob der Sonderfall vorliegt, ist aber fehlerhaft. j repräsentiert nicht die Nummer des Nachbarknotens, sondern den Arrayindex, in dem der Nachbarknoten gespeichert ist. Außerdem ist die Schleifenbedingung falsch, denn die Zeilenanzahl des Arrays entspricht nicht den Zeilenlängen der einzelnen Zeilen.

 

[Terence86]

Ja wie würde es den für die adjListe richtiger Weise aussehen?
Ich habe mir sowas überlegt:

    for(int i = 0 ; i < adjList.length - 1; i++) {
       
        for(int j = 0 ; j < adjList.length -1; j++) {
           
            if(i==j) {
                result.vertexDegrees[i] = result.vertexDegrees[i] + adjList.length + 1;
                // Muss ja die Anzahle pro Zeile nehmen
            } else {
                result.vertexDegrees[i] = result.vertexDegrees[i] + adjList.length;

Für den Grad müsse man ja nur .length benutzten da der die Länge angibt und somit den Grad. Aber meine If-Bedigung ist dann sicher auch falsch. Dachte sowas wie wenn Schleife dabei dann Längenanzahl +1.

 

[Meniskusschaden]

Du musst dir auf jeden Fall bewußt machen, was ein 2D-Array in Java ist, nämlich ein eindimensionales Array, dessen Elemente ebenfalls eindimensionale Arrays sind. Insbesondere sollte auch klar sein, dass all diese eindimensionalen Arrays unterschiedlich lang sein können, was für die allermeisten Graphen auch der Fall ist. In dieser Aufgabe enthält das 2D-Array pro Knoten ein 1D-Array mit den Knotennummern seiner Nachbarknoten. Man kann so zugreifen:

adjList[3].length;  // liefert die Länge der Nachbarnliste des vierten Knotens
adjList[2][3];  // liefert die Knotennummer des vierten Nachbarn des dritten Knotens

Ja wie würde es den für die adjListe richtiger Weise aussehen?

Man iteriert über alle Knoten. Für jeden Knoten iteriert man über seine Nachbarn. Für jeden Nachbarn erhöht man den Grad des Knotens um eins, es sei denn die Knotennummer des Nachbarn entspricht dem aktuellen Knoten, denn dann erhöht man um zwei.

Für den Grad müsse man ja nur .length benutzten da der die Länge angibt und somit den Grad. Aber meine If-Bedigung ist dann sicher auch falsch. Dachte sowas wie wenn Schleife dabei dann Längenanzahl +1.

Nein, da ist nicht nur die Bedingung falsch, sondern alles. Du addierst die Länge in der inneren Schleife. Das ergibt keinen Sinn, denn dann erhöhst du den Grad eines gegebenen Knotens nicht nur einmal um die Länge, sondern einmal pro Nachbarknoten. Außerdem benutzt du dafür nicht die Länge der Nachbarknotenliste, sondern die Anzahl aller Knoten.
Das Addieren der Länge wäre nur in der äußeren Schleife sinnvoll, aber da weißt du noch nicht, ob es den Sonderfall gibt. Die Idee bringt dich hier also nicht weiter.