Anhang 1: Graph-Klasse mit Knotenbezeichnern

Im Abitur begegnet einem bisweilen eine Klasse Graph, die nicht nur - wie schon oft in diesem Skript praktiziert - die Kanten in einer Adjazenzmatrix speichert, sondern zusätzlich die Knoten-Objekte (oder einfach nur die Bezeichner der Knoten) in einem Array. Ihre Aufgabe ist es, eine solche Klasse zu entwickeln, die folgenden Vorgaben entspricht:

• Die Klasse Knoten ist vorgegeben:

public class Knoten {
   private Datenelement inhalt;
 
//Konstruktor
   public Knoten(Datenelement d) {
      inhalt = d; 
   }
 
   //get-Methode
   public Datenelement getInhalt() {
      return inhalt;
   }
 
   //set - Methode
   public void setInhalt(Datenelement d) {
      inhalt=d;
   }
}

• Die Klasse Datenelement enthält nur ein Attribut name vom Typ String und eine entsprechende Methode getName()
• Hier der Beginn der Klasse Graph:

public class Graph {
   //Attribute deklarieren
   private Knoten[] knotenliste;
   private int maxAnzahl; //maximale Knotenanzahl
   private int anzahl; // tatsächliche Knotenanzahl, gibt den Index des ersten freien Platzes im Array an
   private int[][] adjazenzmatrix; 
   //[i][j] != 0 bedeutet es gibt einen Pfeil von i nach j 
 
   //Konstruktor
   public Graph(int maxAnzahl) {
      this.maxAnzahl = maxAnzahl;
      anzahl = 0;
      knotenliste = new Knoten[maxAnzahl];
      adjazenzmatrix = new int [maxAnzahl][maxAnzahl];
 
   }

• Das Feld Knoten ist initial leer (mit null-Werten gefüllt). Werden Knoten gelöscht, so entstehen Lücken (auch mit null gefüllt).
• Nicht vergessen: Beim Löschen eines Knotens müssen die entsprechenden Einträge in der Adjazenzmatrix auf 0 gesetzt werden.
• Die Klasse Graph soll folgende Methoden haben:

  public void knotenEinfuegen(Knoten k)
  public int getAnzahl()
  public Knoten getKnotenAnPosition(int index)
  public void knotenlisteAusgeben()
  public void knotenLoeschen(int index)
  public void setKante(int index1, int index2, int gewicht)
  public void setKante(int index1, int index2, int gewicht12, int gewicht21)
  public int knotenIndexSuchen(String name)
  public void setKante(String knoten1, String knoten2, int gewicht)
  public void setKante(String knoten1, String knoten2, int gewicht12, int gewicht21)

Lösung