Umsetzung mit einer Adjazenzmatrix

Definition

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

Darstellung

In der Matrix wird gespeichert zwischen 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)

Anmerkungen:

• Bei diesem Beispiel handelt es sich um einen ungerichteten Graphen, da alle Kanten in beide Richtungen den gleichen Wert haben.
• Der Graph ist nicht vollständig, da nicht jeder Knoten mit jedem anderen Knoten vebunden ist.
• Alle Kanten sind mit 2 gewichtet. Sollten Kanten mit anderen Gewichtungen hinzukommen, wäre der Graph gewichtet, sonst nicht.

Umsetzung im Quelltext

Deklaration

int [][] matrix;
KNOTEN [] knoten;
...und Andere...

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

die wichtigsten Methoden:

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

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