Umsetzung mit einer Adjazenzmatrix: Unterschied zwischen den Versionen

Version vom 10. Februar 2014, 19:55 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)

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