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
Aus Projektwiki - ein Wiki mit Schülern für Schüler.
(→Definition) |
(→Darstellung) |
||
| (7 dazwischenliegende Versionen von 4 Benutzern werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
==Definition== | ==Definition== | ||
| − | Ein Graph wird in Java mit einer Adjazenzmatrix umgesetzt. Diese ist eine | + | Ein Graph wird in Java mit einer Adjazenzmatrix umgesetzt. Diese ist eine Tabelle, welche durch ein zwei-dimensionales 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. |
==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 26: | Zeile 26: | ||
* 2 = Beispiel für eine Gewichtung (es kann auch ein anderer Wert eingetragen werden) | * 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== | ==Umsetzung im Quelltext== | ||
| − | === | + | ===Deklaration=== |
<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 /> | ||
knoten = new KNOTEN[maxanzahl];<br /></code> | knoten = new KNOTEN[maxanzahl];<br /></code> | ||
--> maxanzahl ist ein Parameter, der zum Erzeugen der Matrix benötigt wird.<br /> | --> maxanzahl ist ein Parameter, der zum Erzeugen der Matrix benötigt wird.<br /> | ||
| − | <code>aktAnzahlKn = 0;</code> | + | <code> aktAnzahlKn = 0;</code> |
| + | |||
===Methoden=== | ===Methoden=== | ||
| − | + | die wichtigsten Methoden: | |
| − | #[[KnotenEinfuegen]] | + | #[[/KnotenEinfuegen/]] |
| − | #[[KnotenNummer]] | + | #[[/KnotenNummer/]] |
| − | #[[KanteEinfuegen]] | + | #[[/KanteEinfuegen/]] |
| − | #[[Ausgeben]] | + | #[[/Ausgeben/]] |
...........noch in Bearbeitung............ | ...........noch in Bearbeitung............ | ||
Aktuelle Version vom 12. März 2014, 09:30 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)
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;
...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............
