Umsetzung mit einer Adjazenzmatrix

Definition

Ein Graph wird in Java mit einer Adjazenzmatrix umgesetzt. Diese ist eine zwei-Dimensionale Liste, welche durch ein doppeltes Array umgesetzt wird: int [][] matrix; Die Spalten und Zeilen sind jeweils einem bestimmten Knoten zugeordnet

Darstellung

In der Matrix wird gespeichert von welchen Knoten Kanten existieren und welche Gewichtung diese besitzen.

      LI|UL|SA|AU|MU|RO|RE|NU|HO|WU|FD| 
   LI|-1| 2|  |  |  |  |  |  |  |  |  | 
   UL| 2|-1| 2| 2|  |  |  |  |  | 2|  | 
   SA|  | 2|-1|  |  |  |  |  |  |  |  | 
   AU|  | 2|  |-1| 2|  |  |  |  |  |  | 
   MU|  |  |  | 2|-1| 2| 2| 2|  |  |  | 
   RO|  |  |  |  | 2|-1|  |  |  |  |  | 
   RE|  |  |  |  | 2|  |-1| 2| 2|  |  | 
   NU|  |  |  |  | 2|  | 2|-1| 2| 2|  | 
   HO|  |  |  |  |  |  | 2| 2|-1| 2|  | 
   WU|  | 2|  |  |  |  |  | 2| 2|-1| 2| 
   FD|  |  |  |  |  |  |  |  |  | 2|-1|

Bedeutungen:

• LI-UL-SA-... = Kurzbeschreibungen für die Städte
• -1 = Es kann keine Kante Geben, da es keine Verbindung zwischen ein und der Selben Stadt existieren kann
• | | = es existiert keine Kante
• 2 = Beispiel für eine Gewichtung (es kann auch ein anderer Wert eingetragen werden)

Anmerkung: bei diesem Beispiel handelt es sich um einen ungerichteten Graphen, da er über eine Diagonale (von links oben nach rechts unten) gespiegelt werden kann, d.h. alle Kanten sind in alle Richtungen "zugänglich"

Umsetzung im Quelltext

Deklarisierung

int [][] matrix;
KNOTEN [] knoten;


Initialisierung

matrix = new int [maxanzahl][maxanzahl];
knoten = new KNOTEN[maxanzahl];
--> maxanzahl ist ein Parameter, der zum Erzeugen der Matrix benötigt wird.
int aktAnzahlKn = 0;

Methoden

nach der Deklaration und Initialisierung der beiden Arrays und einigen weiteren notwendigen Attributen (z.B. aktuelle Anzahl Knoten in der Liste) können verschiedenste Methoden geschrieben werden:

1. KnotenEinfuegen
2. KnotenNummer
3. KanteEinfuegen
4. Ausgeben

...........noch in Bearbeitung............