Wie löse ich solch Java Aufgabe?

1 Antwort

regex9
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Java, BlueJ, Code
09.03.2023, 14:56

Grundvoraussetzung ist erst einmal, dass du die Aufgabe verstehst. Das heißt, du musst bspw. zu den Fachbegriffen, die dir nicht bekannt sind, recherchieren. Die Programmierung bleibt so lange außen vor, bis du einen genauen Plan davon hast, was du tun musst.

Ich werde folgend nur auf ein paar Punkte eingehen, die die Minimalanforderungen abdecken.

1) Bei einer Adjazenzmatrix handelt es sich einfach ausgedrückt um eine Matrix / Tabelle, anhand der du einen Graph bilden kannst. Zum einen kannst du die Anzahl der Vertices ermitteln und zum anderen deren Verbindung.

Beispiel:

  | A | B |
-----------
A | 0 | 5 |
B | 2 | 0 |

Der Graph besteht aus zwei Vertices (A, B). Eine Verbindung (Edge) zwischen zwei Vertices wird durch eine Zahl größer als 0 angedeutet. Wenn es keine Verbindung gibt, wird dies mit einer 0 gekennzeichnet.

In meinem Beispiel wird ein gerichteter Graph mit Kantengewichten dargestellt. Die Kosten der Kante von A nach B betragen 5, von B nach A hingegen 2.

A <- 2 ---------- 5 -> B

Für die CSV-Datei müsstest du erst einmal das Format definieren, damit du sie richtig einlesen kannst. Du könntest die Header mit speichern oder du belässt es nur bei den Werten. Je nachdem musst du beim Einlesen Daten filtern oder nicht.

Beispiel:

,A,B
A,0,1
B,1,0

Ebenso müsstest du dir überlegen, in welcher Datenstruktur du die Daten speicherst. Ein zweidimensionales Integer-Array wäre eine Möglichkeit.

Das Einlesen einer Datei kann man leicht mittels BufferedReader bewerkstelligen. Aber vielleicht habt ihr von eurem Dozent noch eine andere Methodik zur Hand bekommen. Es führen viele Wege nach Rom.

try (var reader = new BufferedReader(new FileReader("data.csv"))) {
  String row;

  while ((row = reader.readLine()) != null) {
    String[] columns = row.split(",");
    // ...
  }
}
catch (IOException ex) {
  ex.printStackTrace();
}

In diesem Fall wird eine CSV-Datei zeilenweise eingelesen und jede Zeile anhand ihres Trennzeichens noch einmal aufgetrennt. Was du daraus machst, ist dir überlassen.

Du könntest übrigens auch jede Zeile anhand einer Scanner-Instanz auswerten.

try (var rowScanner = new Scanner(row)) {
  rowScanner.useDelimiter(",");
  // ...
}

Der try-Block, den ich in beiden Beispielen verwende, sorgt dafür, dass die Streams / Ressourcen, die von den beiden Objekten (Scanner, BufferedReader) geöffnet werden, nach Nutzung auf jeden Fall auch wieder geschlossen werden.

Die Hauptfunktion von try-catch liegt jedoch darin, erwartete Ausnahmefälle zu behandeln. Wenn das Programm beispielsweise die CSV-Datei nicht findet oder während des Lesens ein Zugriffsfehler auftritt, wird dieser abgefangen. In dem Fall würde der Programmfluss sofort in den catch-Block springen, in dem definiert wird, wie es weitergehen soll. Im obigen Beispiel werden nur Fehlerinformationen in die Konsolenausgabe geschrieben.

2) Die Berechnung der Distanzen und Exzentritäten (= Distanz zum weit entferntesten Vertex eines Vertex X) zwischen den verschiedenen Vertices lässt sich mit Schleifen und Arrays lösen (oder du baust dir gleich von Beginn an die Graphenstruktur nach, siehe Punkt 4). Speicher dir alle alle Distanzen von einem Vertex X zu seinen anderen Vertices im Graph in einem Array. Dann kannst du nachfolgend nach dem größten Wert im Array suchen.

Überlege dir dabei, wie du Schritt für Schritt vorgehen würdest, wenn du beispielsweise einen Kartenstapel durchgehen und die Karte, mit der höchsten Wertigkeit finden müsstest. Oder noch besser: Überlege dir, wie du jemand Ahnungslosen anleiten würdest, die Karte mit der höchsten Wertigkeit zu finden.

3) Radius, Durchmesser, etc. sind leicht berechenbar, sobald du die äußersten Vertices ermittelt hast. Das heißt du kannst die Berechnungen der vorherigen Aufgabe nutzen, indem du dir einfach die Exzentritäten je Vertex merkst. Die größte Exzentrität bildet den Durchmesser des Graphen ab.

4) Für die Berechnung der Komponente (größte Anzahl zusammenhängender Knoten), Artikulationen (Vertices, die bei Entfernung die Verbindung zwischen Teilgraphen kappen) und Brücken (Kanten, die bei Entfernung die Verbindung zwischen Teilgraphen kappen) wäre es wohl ganz praktisch, den Graph als Programmstruktur erst nachzubauen.

Klassen und Objekte müssten hierfür bekannt sein. Die Implementation kann man im Grundaufbau ganz einfach halten.

class Vertex {
  String name;
  Edge[] edges = new Edge[2];
}

class Edge {
  int weight;
  Vertex[] vertices = new Vertex[2];
}

Und um die Struktur komfortabel zu machen, ergänzt man vielleicht Methoden wie getNeighbourVertices, addNeighbourVertex, o.ä..

Im Anschluss erstellt man anhand der Matrix den konkreten Graph, über den man nachfolgend iterieren/traversieren kann. Eine Tiefensuche sollte in diesem Zusammenhang nützlich sein.

Als Hilfsmittel zur Lösung der Aufgaben würde ich auf jeden Fall empfehlen, Skizzen (eines oder mehrerer Beispielgraphen) anzulegen. Solche Aufgaben mit bildlicher Repräsentation zu lösen, ist in der Regel einfacher.

Je Aufgabenteil (Bsp.: Berechne Radius, berechne Exzentrität, ...) würde ich eine Methode erstellen. Um ihren Programmablauf zu definieren, würde ich dir raten, Struktogramme oder Programmablaufpläne anzulegen. Du machst es dir so viel leichter, denn in dem Schritt musst du dir noch keine sprachlichen Zwänge auferlegen und kannst dich auf die wesentliche Logik konzentrieren. Die Formulierung in Code erfolgt erst viel später.

Im Übrigen findest du auf Wikipedia noch einmal Erklärungen (bildlich, textuell, mathematisch) zu den einzelnen Themen (Graphentheorie, Trenner, Zusammenhang, usw.).