3. Die Datenstruktur Graph 3.2 Repräsentation von Graphen · 2019. 2. 11. · Informatik 11 3. Datenstruktur Graph 3.2 Repräsentation von Graphen Beispiel 1: Graph Adjazenzmatrix

3. Die Datenstruktur Graph3.2 Repräsentation von Graphen

Für die Darstellung eines Graphen eignet sich die sogenannte Adjazenzmatrix .

Dabei handelt es sich um eine Tabelle, in der die Zeilen- und Spaltenüberschriften die Knotenbezeichner sind.

In eine Zelle wird eine 1 eingetragen, wenn es zwischen den zugehörigen Knoten eine Kante gibt.

Informatik 11 - 3. Die Datenstruktur Graph – 3.2 Repräsentation von Graphen

Informatik 11 3. Datenstruktur Graph 3.2 Repräsentation von Graphen

Beispiel 1:Graph Adjazenzmatrix

v1 v2 v3 v4 v5 v6

v1 1 1 1

v2 1 1

v3 1 1

v4 1 1 1

v5 1

v6 1

In eine Zelle wird eine 1 eingetragen, wenn es zwischen den zugehörigen Knoten eine Kante gibt. Die Adjazenzmatrix ist symmetrisch zur Hauptdiagonalen.



v1 v2 v3 v4 v5 v6

v1 1 1 1

v2

v3 1

v4 1 1

v5 1

v6 1

Bei einem gerichteten Graphen muss die Adjazenzmatrix nicht mehr symmetrisch zur Hauptdiagonalen sein.



v1 v2 v3 v4 v5 v6

v1 10 20 10

v2 10 20 10

v3 20 20 10

v4 10 10 30

v5 10 40

v6 30 40

Bei einem gewichteten Graphen trägt man die Kantenwerte ein.


Implementierung einer Matrix in Java:Beispiel: (keine Adjazenzmatrix!)

1 2 34 5 6

int[][] mat;public Matrix(){

mat = new int [zeilen] [spalten];

mat[0] = Feld mit 3 Elementen

mat[1] = Feld mit 3 Elementen


Implementierung einer Matrix in Java:

public class Matrix{int zeilen = 2;int spalten = 3;int[][] mat;

public Matrix(){mat = new int [zeilen] [spalten];mat[0][0] = 1;mat[0][1] = 2;mat[0][2] = 3;mat[1][0] = 4;mat[1][1] = 5;mat[1][2] = 6;

}}

1 2 34 5 6


Ausgabe der Matrix mit verschachtelten Schleifen:

public void ausgabe(){for(int i = 0; i< zeilen; i++){ for(int j = 0; i<spalten; j++){

System.out.print("mat[" + i + "] [" + j + "] = " + mat[i][j]+" ");

}System.out.println();

}

1 2 34 5 6


Übung 1 – Matrizen in Java

a)Übertrage das Beispiel für eine Matrix mit der Methode zur Ausgabe in ein BlueJ Projekt.

Implementiere eine Methode boolean suchen(int zahl), die ausgibt, ob eine bestimmte Zahl in der Matrix vorhanden ist und für diesen Fall die Position ausgibt.

b)Teste und untersuche auch das BlueJ ProjektMatrixScanner im Ordner Lösungen.


Modellieren eines Graphen:


Die Klasse GRAPH_MATRIX verwaltet die Knoten und Kanten und stellt eine Methode zur formatierten Ausgabe der Matrix bereit.


Verwalten von Knoten und Kanten:

A B C D

A 0 5 8 3

B 5 0 -1 5

C 8 -1 0 -1

D 3 5 -1 0

Knotenfeld:knoten[0] Bezeichner "A" Knotennummer 0;knoten[1] Bezeichner "B" Knotennummer 1;

Matrix:0 für die Elemente der Hauptdiagonale;

-1 steht für eine nicht vorhandene Kante, diese Zelle bleibt bei der Ausgabe leer.


Einfügen eines neuen Knotens :

A B C D E

A 0 5 8 3 -1

B 5 0 -1 5 -1

C 8 -1 0 -1 -1

D 3 5 -1 0 -1

E -1 -1 -1 -1 0

Knotenfeld ergänzen, vorausgesetzt, der Knoten ist noch nicht vorhanden und die maximale Anzahl ist nicht überschritten.

Matrix:0 und -1 in der neuen Spalte und der neuen Zeile ergänzen.


Einfügen einer neuen Kante :

A B C D E

A 0 5 8 3 -1

B 5 0 -1 5 9

C 8 -1 0 -1 -1

D 3 5 -1 0 -1

E -1 9 -1 -1 0

Matrix:Gewichtung eintragen


Übung 2 – Implementieren einer Matrix für einen GraphenVorlage: Graph_Matrix_Vorlage

In der Vorlage ist bereits eine Methode zur formatierten Ausgabe implementiert.

Ergänze das Projekt um die benötigten Attribute und um die fehlenden Methoden KnotenEinfuegen und KanteEinfuegen.

Eine kurze Hilfestellung findest auf der folgenden Seite. Im Quelltext sind in den Kommentaren ebenfalls Erläuterungen notiert.


Übung 2 – Implementieren einer Matrix für einen GraphenVorlage: Graph_Matrix_Vorlage

Klasse GRAPH_MATRIXvoid KnotenEinfuegen(String bezeichner)Wenn die maximale Anzahl an Knoten erreicht wird oder der Knoten bereits eingefügt ist, erfolgt kein Einfügen.

Ob der Knoten bereits eingefügt ist, findet man mit der Methode KnotenNummer(bezeichner) heraus.

In der Matrix soll an der Position der Diagonalen eine 0 stehen.

An den übrigen Plätzen (d.h. in der Spalte und in der Zeile des neuen Knotens) bis zu dieser Position wird mithilfe einer geeigneten Schleife in die Matrix jeweils eine -1 eingefügt, die in der Methode Ausgabe() die Ausgabe einer Leerstelle bewirkt.

Klasse GRAPH_MATRIXvoid KanteEinfuegen(String von, String nach, int gewichtung)In der Methode legt man zwei int-Attribute vonNummer und nachNummer fest, denen die Knotennummern der Knoten von und nach zugeordnet werden.Falls diese Knoten in der Knotenliste auftauchen (d.h. die Knotennummer ist nicht -1) und nicht identisch sind, ergänzt man in der Matrix die beiden Einträge.

Ausführliche Hinweise findest du auf den nächsten Seiten und im Buch auf den Seiten103 -105.


Knoten und Kanten einfügen – detaillierte Beschreibung

Graph Knotenliste

Adjazenzmatrix

A B C D EA 0 1 1 1 -1B 1 0 1 -1 -1C 1 1 0 -1 1D 1 -1 -1 0 1E -1 -1 1 1 0

A B C D E


Knoten und Kanten einfügen – detaillierte Beschreibung

Jeder Knoten hat eine Knotennummer, die mit dem Arrayindex identisch ist.Noch nicht vorhandene Knoten erhalten die Nummer -1

Beispiel: Knoten E in die Knotenliste einfügen

A B C D0 1 2 3

public int KnotenNummer(String bezeichner) { int ergeb =-1; for (int i=0; (i < anzahlKnoten) && (ergeb == -1); i++){

if (knoten[i].BezeichnungGeben().equals(bezeichner)) { ergeb = i;

}} return ergeb;

}

Der Aufruf KnotenNummer(“E“) liefert den Wert -1 zurück.


Knoten und Kanten einfügen – detaillierte BeschreibungBeispiel: Knoten E in die Knotenliste einfügen

A B C D E0 1 2 3 4

A B C D EA 0 1 1 1 -1B 1 0 1 -1 -1C 1 1 0 -1 -1D 1 -1 -1 0 -1E -1 -1 -1 -1 0

Der Knoten wird dem Feld zugefügt und die Einträge in der Matrix werden ergänzt.

anzahlKnoten hat vor dem Einfügen von E den Wert 4.

Also kann E so eingefügt werden:

knoten[anzahlKnoten] = new KNOTEN(bezeichner);


Knoten und Kanten einfügen – detaillierte BeschreibungBeispiel: Knoten E in die Knotenliste einfügen

Der Knoten wird dem Feld zugefügt und die Einträge in der Matrix werden

ergänzt.

public void KnotenEinfuegen(String bezeichner) {

if ((anzahlKnoten < knoten.length) && (KnotenNummer(bezeichner) == -1)) {

knoten[anzahlKnoten] = new KNOTEN(bezeichner);

matrix[anzahlKnoten][anzahlKnoten] = 0;

for (int i=0; i<anzahlKnoten; i++) {

matrix[anzahlKnoten][i] = -1; matrix[i][anzahlKnoten] = -1;

}

anzahlKnoten = anzahlKnoten + 1;

}

}

A B C D E0 1 2 3 4

A B C D EA 0 1 1 1 -1B 1 0 1 -1 -1C 1 1 0 -1 -1D 1 -1 -1 0 -1E -1 -1 -1 -1 0


Knoten und Kanten einfügen – detaillierte BeschreibungBeispiel: Kante DE in die Matrix einfügen

A B C D EA 0 1 1 1 -1B 1 0 1 -1 -1C 1 1 0 -1 1D 1 -1 -1 0 -1E -1 -1 1 -1 0

Adjazenzmatrix vorher:



A B C D EA 0 1 1 1 -1B 1 0 1 -1 -1C 1 1 0 -1 1D 1 -1 -1 0 1E -1 -1 1 1 0

Adjazenzmatrix nachher:



Knotennummern von D und E ermitteln:

A B C D E0 1 2 3 4

int vonNummer, nachNummer; vonNummer = KnotenNummer(von); nachNummer = KnotenNummer(nach);

public int KnotenNummer(String bezeichner) { int ergeb =-1; for (int i=0; (i < anzahlKnoten) && (ergeb == -1); i++){

if (knoten[i].BezeichnungGeben().equals(bezeichner)) { ergeb = i;

}} return ergeb;

}



Einträge in der Matrix ergänzen:

public void KanteEinfuegen(String von, String nach, int gewichtung) {

int vonNummer, nachNummer;

vonNummer = KnotenNummer(von);

nachNummer = KnotenNummer(nach);

if ((vonNummer!=-1) && (nachNummer!=-1) && (vonNummer!=nachNummer)) {

matrix[vonNummer][nachNummer] = gewichtung;

matrix[nachNummer][vonNummer] = gewichtung;

}

}

A B C D EA 0 1 1 1 -1B 1 0 1 -1 -1C 1 1 0 -1 1D 1 -1 -1 0 1E -1 -1 1 1 0


Übung 3 – Beispiele für GraphenGraph_Matrix_Beispiele (im Ordner Lösungen)

Teste die Methoden für die gegebenen Beispielgraphen.


Modellierung und Implementierung mit Listen

Gibt es in einem Graphen viele Knoten aber wenig Kanten, so hat die Adjazenzmatrix wenig Einträge. Man spricht in diesem Fall von einemdünnen Graphen.

v1 v2 v3 v4 v5 v6

v1 1 1 1

v2 1 1

v3 1 1

v4 1 1 1

v5 1

v6 1

Beispiel:


Modellierung und Implementierung mit Listen

In diesem Fall bietet es sich an, die Knoten und Kanten in einfach verketteten Listen zu verwalten:


Übung 4 (Vertiefung) – Implementierung mithilfe der Javaklasse VectorErgänze in der Vorlage Graph_Liste_Vector_0 den fehlenden Quelltext.Die Listen werden mit der Javaklasse Vector implementiert.


Übung 4 (Vertiefung) – Implementierung mithilfe der Javaklasse VectorAusgabe des erzeugten Graphen:

A: M, 64; UL, 59;F: KA, 127; WÜ, 131;FD: WÜ, 98;HO: WÜ, 192; N, 116; R, 166;KA: F, 127; S, 53;LI: UL, 126;M: A, 64; N, 163; R, 117; RO, 60;N: WÜ, 104; R, 80; HO, 116; M, 163;PA: R, 72;R: N, 80; PA, 72; HO, 166; M, 117;RO: M, 60;S: UL, 103; KA, 53; WÜ, 155;UL: A, 59; WÜ, 165; LI, 126; S, 103;WÜ: F, 131; N, 104; HO, 192; FD, 98; UL, 165; S, 155;


Übung 5 (Vertiefung) – Implementierung ohne die Javaklasse VectorErgänze in der Vorlage Graph_Liste_0 den fehlenden Quelltext.Die Listen werden ohne Verwendung einer Javaklasse implementiert.

Documents

3. Die Datenstruktur Graph 3.2 Repräsentation von Graphen · 2019. 2. 11. · Informatik 11 3. Datenstruktur Graph 3.2 Repräsentation von Graphen Beispiel 1: Graph Adjazenzmatrix