Umsetzung mit einer Adjazenzmatrix

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

Umsetzung

Damit jeder Knoten (in unserem Beispiel S-Bahnhöfe, bzw. Städte) eine eindeutige Identifikationsnummer hat, erzeugen wir noch ein zweites Array, in dem die Knotennamen und die dazugehörigen Nummern gespeichert sind. KNOTEN [] knoten; Damit erfüllen wir das Prinzip der Aufgabentrennung. In der Matrix wird dann 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)

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