Umsetzung mit einer Adjazenzmatrix: Unterschied zwischen den Versionen

Version vom 10. Februar 2014, 19:59 Uhr

Definition

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

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)

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.
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............