Dieses Wiki, das alte(!) Projektwiki (projektwiki.zum.de)
wird demnächst gelöscht.
Bitte sichere Deine Inhalte zeitnah,
wenn Du sie weiter verwenden möchtest.
Gerne kannst Du natürlich weiterarbeiten
im neuen Projektwiki (projekte.zum.de).Umsetzung mit einer Adjazenzmatrix: Unterschied zwischen den Versionen
(→Definition) |
(→Definition) |
||
| Zeile 1: | Zeile 1: | ||
==Definition== | ==Definition== | ||
| − | Ein Graph wird in Java mit einer Adjazenzmatrix umgesetzt. Diese ist eine zwei- | + | Ein Graph wird in Java mit einer Adjazenzmatrix umgesetzt. Diese ist eine zwei-Dimensionale Liste, welche durch ein doppeltes Array umgesetzt wird: |
int [][] matrix; | int [][] matrix; | ||
Die Spalten und Zeilen sind jeweils einem bestimmten Knoten zugeordnet | Die Spalten und Zeilen sind jeweils einem bestimmten Knoten zugeordnet | ||
Version vom 11. Februar 2014, 15:17 Uhr
Inhaltsverzeichnis |
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];
--> maxanzahl ist ein Parameter, der zum Erzeugen der Matrix benötigt wird.
knoten = new KNOTEN[maxanzahl];
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:
...........noch in Bearbeitung............
