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) |
|||
| Zeile 5: | Zeile 5: | ||
==Darstellung== | ==Darstellung== | ||
| − | In der Matrix wird gespeichert | + | 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|UL|SA|AU|MU|RO|RE|NU|HO|WU|FD| | ||
| Zeile 27: | Zeile 27: | ||
Anmerkung: | Anmerkung: | ||
| − | + | Bei diesem Beispiel handelt es sich um einen ungerichteten Graphen, da alle Kanten in beide Richtung den gleichen Wert haben. | |
==Umsetzung im Quelltext== | ==Umsetzung im Quelltext== | ||
| Zeile 33: | Zeile 33: | ||
<code>int [][] matrix;<br /> | <code>int [][] matrix;<br /> | ||
KNOTEN [] knoten;<br /></code> | KNOTEN [] knoten;<br /></code> | ||
| + | ...und Andere... | ||
===Initialisierung=== | ===Initialisierung=== | ||
<code>matrix = new int [maxanzahl][maxanzahl];<br /> | <code>matrix = new int [maxanzahl][maxanzahl];<br /> | ||
| Zeile 40: | Zeile 41: | ||
===Methoden=== | ===Methoden=== | ||
| − | + | die wichtigsten Methoden: | |
#[[/KnotenEinfuegen/]] | #[[/KnotenEinfuegen/]] | ||
Version vom 11. Februar 2014, 20:08 Uhr
Inhaltsverzeichnis |
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)
Anmerkung: Bei diesem Beispiel handelt es sich um einen ungerichteten Graphen, da alle Kanten in beide Richtung den gleichen Wert haben.
Umsetzung im Quelltext
Deklarisierung
int [][] matrix;
...und Andere...
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
die wichtigsten Methoden:
...........noch in Bearbeitung............
