Graphen und ihre Implementierung Klaus Becker 2007

Graphenund ihre Implementierung

Klaus Becker

2007

2 Graphen

Zielsetzung: Am Beispiel von Graphen Standardalgorithmen zur Lösung von Standardproblemen erkunden eine vorgegebene Klasse zur Erledigung von Standardaufgaben

benutzen (und erweitern)

TR

KO

RB

BI

KL

AZ

MZ

FT

SP

128

98

54

28 35

3533

3648

48 31

116

3 Teil 1

Graphen und Graphenprobleme

4 tratsCH trATsch

23. Bundeswettbewerb Informatik:

siehe: http://www.mk-intern.bildung-lsa.de/Bildung/be-bundeswettbewerbinformatik2004_2005.pdf

5 tratsCH trATsch

23. Bundeswettbewerb Informatik:

6 Aufgabe

Stellen Sie die in der Tabelle abgebildeten Informationen möglichst übersichtlich grafisch dar.

Über wen darf A Schlechtes schreiben, ohne einen Charmefehler zu riskieren?

7 Graphen

Graphen sind mathematische Strukturen, mit deren Hilfe man Objekte und die sie verbindenden Beziehungen beschreibt. Ein Graph besteht dabei aus sog. Knoten und Kanten. Die Knoten repräsentieren die Objekte, die Kanten die Beziehungen zwischen den Objekten.

A

B

C

D

E

F

G H

Mathematisch: G = (V, E)

V = {A, B, C, D, E, F, G} ist die Menge der Knoten.

E = {(A,B), (A,E), (B,C), ..., (H,D)} ist die Menge der Kanten.

8 Typen von Graphen

Je nach Anwendung ist es sinnvoll, Kanten gerichtet oder ungerichtet zu modellieren. Bei gerichteten Graphen werden in der Regel auch sog. Schlingen zugelassen. Werden die Kanten mit zusätzlichen Gewichten versehen, so spricht man von gewichteten oder bewerteten Graphen.

A

B

C

D

E

F

G H

A

B

C

D

E

F

G H

128

17

11

5

3

5

68

gerichteter, unbewerteter Graph

ungerichteter, bewerteter Graph

9 Klassische Graphenprobleme

A

B

C

D

E

F

G H

Wege, Erreichbarkeit:Gibt es einen Weg zwischen Knoten X und Knoten Y?

Kann Tratsch von A nach H gelangen? Kann Tratsch von H nach A gelangen?


A

B

C

D

E

F

G H

Zusammenhang, Zyklen:Gibt es von jedem Knoten zu jedem anderen Knoten einen Weg entlang der Kanten?Gibt es Zyklen (d. h. geschlossene Wege) innerhalb des Graphen?

Von H gibt es keinen Weg zu A. Der Graph ist nicht stark zusammenhängend.

Der Graph enthält Zyklen, z. B. C -> G -> H -> D -> C


Euler-Weg / Euler-Kreis:Gibt es einen (geschlossenen) Weg, der jede Kante genau einmal besucht?

Königsberger Brückenproblem Haus des Nikolaus


Hamilton-Kreis / Rundreise:Gibt es einen geschlossenen Weg, der jeden Knoten genau einmal besucht?

siehe: http://www.tsp.gatech.edu/d15sol/d15map.html

Rundreise durch alle 15112 Gemeinden in Deutschland


Abstände:Wie viele Stationen liegen zwischen einem Startknoten X und einem Zielknoten Y?

siehe: http://www.mvv-muenchen.de/web4archiv/objects/download/2/schnellbahnnetz_2007.pdf


kürzeste Wege:Welcher Weg zwischen Knoten X und Knoten Y ist der kürzeste?

kürzester Weg von SP nach KO: SP -> FT -> AZ -> BI -> RB -> KO

TR

KO

RB

BI

KL

AZ

MZ

FT

SP

128

98

54

28 35

3533

3648

48 31

116

15 Teil 2

GraphenalgorithmenFallstudie: Wege in Graphen

16 Problem 1: Graphen durchlaufen

Problem: Welche Knoten kann man von einem Startknoten aus mit einem Weg entlang der Kanten erreichen?

A

B

C

D

E

F

G H

17 Problem 2: Abstände bestimmen

Problem: Wie viele Knoten liegt ein Zielknoten vom Startknoten entfernt?

18

Problem 3: kürzeste Wege bestimmen

Problem: Welcher Weg von einem Startknoten zu einem Zielknoten ist am kürzesten?

TR

KO

RB

BI

KL

AZ

MZ

FT

SP

128

98

54

28 35

3533

3648

48 31

116

19 Aufgabe

Überlegen Sie sich selbst ein Verfahren, wie man eines der vorgestellten Probleme lösen kann.

Tipp: Nutzen Sie die Möglichkeit, Zusatzinformationen an Knoten zu schreiben.

20 Aufgabe

Sie können sich auch auf den Webseiten des "(Math)e(prism)a" informieren. Hier finden Sie Algorithmen zur Lösung der drei vorgestellten Probleme. Quelle: http://www.matheprisma.uni-wuppertal.de/Module/Graphen/index.htm

Benutzen Sie das Programm "Shortest Path Animation", um die Grundidee des Algorithmus von Dijkstra zur Lösung von Problem 3 herauszufinden. Quelle: http://www.educeth.ch/informatik/puzzles/routing/docs/dijkstra.exe

21 Algorithmus "Graph durchlaufen"

Quelle: http://www.matheprisma.uni-wuppertal.de/Module/Graphen/index.htm

{Eingabe: Graph G; Startknoten s des Graphen}

für alle Knoten w markiere w als nicht besuchtfüge s in eine (zunächst leere) Datenstruktur D ein solange D nicht leer ist entnimm einen Knoten w aus D für alle Kanten {w,u} falls u nicht markiert ist markiere u füge u in D ein

{Ausgabe: Markierungen für alle Knoten w von G; ein Knoten ist genau dann als 'besucht' markiert, wenn er üben einen Weg mit s verbindbar ist}

22 Beispiel

S

C

EA

D

B F

markiere alle Knot. als nicht besucht (hier 0) markiere S als besucht (hier 1) füge s in e. Datenstruktur D (hier grün) ein

S

C

EA

D

B F

1

0

0 0

0

00

S

C

EA

D

B F

1

0

0 0

0

00

entnimm einen Knoten w (hier blau) aus D für alle Kanten {w,u} falls u nicht markiert ist markiere u füge u in D ein

S

C

EA

D

B F

1

1

0 0

0

01

Vorbereitungsschritt

Wiederholungsschritt

23 Beispiel

S

C

EA

D

B F

1

1

0 0

1

01


S

C

EA

D

B F

1

1

0 0

0

01 S

C

EA

D

B F

1

1

0 0

1

01

S

C

EA

D

B F

1

1

0 0

1

11

S

C

EA

D

B F

1

1

0 0

1

11

S

C

EA

D

B F

1

1

1 0

1

11

Auswahlstrategie

First InFirst Out

-> Breitensuche

Auswahlstrategie

Last InFirst Out

-> Tiefensuche

24 Beispiel


S

C

EA

D

B F

1

1

1 0

1

11

S

C

EA

D

B F

1

1

1 0

1

11

S

C

EA

D

B F

1

1

1 0

1

11

S

C

EA

D

B F

1

1

1 0

1

11

Ergebnis:Von S aus gibt es Wege zu den folgenden Knoten: A, B, C, D, E.

25 Algorithmus von Moore


für alle Knoten w setze dg(w) = ∞ setze dg(s) = 0 füge s in eine (zunächst leere) Datenstruktur D ein solange D nicht leer ist entnimm einen Knoten w aus D für alle Kanten {w,u} falls dg(u) = ∞ setze dg(u) = dg(w)+1 füge u in D ein

{Ausgabe: Abstand d(w) aller Knoten w von s; Knoten mit d(w) = ∞ sind nicht mit s verbindbar}


26 Beispiel

S

C

EA

D

B F

für alle Knoten w setze dg(w) = ∞ setze dg(s) = 0 füge s in eine Datenstruktur D (hier grün) ein

entnimm einen Knoten w (hier blau) aus D für alle Kanten {w,u} falls dg(u) = ∞ setze dg(u) = dg(w)+1 füge u in D ein



S

C

EA

D

B F

0

∞

∞ ∞

∞

∞∞ S

C

EA

D

B F

0

1

∞ ∞

∞

∞1

S

C

EA

D

B F

0

∞

∞ ∞

∞

∞∞

27 Beispiel


S

C

EA

D

B F

0

1

∞ ∞

∞

∞1

S

C

EA

D

B F

0

1

∞ ∞

2

∞1

S

C

EA

D

B F

0

1

∞ ∞

2

∞1

S

C

EA

D

B F

0

1

∞ ∞

2

21

S

C

EA

D

B F

0

1

∞ ∞

2

21

S

C

EA

D

B F

0

1

3 ∞

2

21

28 Beispiel


Ergebnis:Von S aus beträgt der Abstand zu C und E jeweils 1, zu A und D jeweils 2, zu B 3 und zu F ∞.

S

C

EA

D

B F

0

1

3 ∞

2

21

S

C

EA

D

B F

0

1

3 ∞

2

21

S

C

EA

D

B F

0

1

3 ∞

2

21

S

C

EA

D

B F

0

1

3 ∞

2

21

29 Algorithmus von Dijkstra


für alle Knoten w setze dg(w) = ∞ setze dg(s) = 0 füge s in eine (zunächst leere) Datenstruktur D ein solange D nicht leer ist entnimm einen Knoten w mit minimalem dg(w) aus D für alle Kanten {w,u} falls dg(u) = ∞ füge u in D ein falls dg(u) > dg(w) + g({w,u}) setze dg(u) = dg(w)+g({w,u})

{Ausgabe: gewichteter Abstand dg(w) aller Knoten w vom Startknoten s}


30 Beispiel

für alle Knoten w setze dg(w) = ∞ setze dg(s) = 0 füge s in eine Datenstruktur D (hier grün) ein

entnimm e. Knoten w m. min. dg(w) aus D für alle Kanten {w,u} falls dg(u) = ∞ füge u in D ein falls dg(u) > dg(w) + g({w,u}) setze dg(u) = dg(w)+g({w,u})



S

C

EA

D

B F

0

∞

∞ ∞

∞

∞∞ S

C

EA

D

B F

0

20

∞ ∞

∞

∞2

S

C

EA

D

B F

0

∞

∞ ∞

∞

∞∞S

C

EA

D

B F

1320

2 19

16 2

10

1 8

3

4

1320

2 19

16 2

10

1 8

3

4

1320

2 19

16 2

10

1 8

3

4

1320

2 19

16 2

10

1 8

3

4

31 Beispiel


S

C

EA

D

B F

0

20

∞ ∞

∞

∞2

S

C

EA

D

B F

0

20

∞ ∞

212

S

C

EA

D

B F

0

20

∞ ∞

212

S

C

EA

D

B F

0

20

∞ ∞

30

212

S

C

EA

D

B F

0

20

∞ ∞

30

212

S

C

EA

D

B F

0

20

∞

23

212

1320

2 19

16 2

10

1 8

3

4

1320

2 19

16 2

10

1 8

3

4

1320

2 19

16 2

10

1 8

3

4

1320

2 19

16 2

10

1 8

3

4

1320

2 19

16 2

10

1 8

3

4

1320

2 19

16 2

10

1 8

3

4

∞

∞

∞

32 Beispiel


Ergebnis:Von S aus beträgt der kürzeste Weg zu E 2, zu C 20, zu A 21, zu D 23, zu B 31 und zu F ∞.

S

C

EA

D

B F

0

20

∞

23

212

S

C

EA

D

B F

0

20

31 ∞

23

212

S

C

EA

D

B F

0

20

31 ∞

23

212

S

C

EA

D

B F

0

20

31 ∞

23

212

1320

2 19

16 2

10

1 8

3

4

1320

2 19

16 2

10

1 8

3

4

1320

2 19

16 2

10

1 8

3

4

1320

2 19

16 2

10

1 8

3

4

∞

33 Teil 3

Implementierung von Graphen

34

TR

KO

RB

BI

KL

AZ

MZ

FT

SP

128

98

54

28 35

3533

3648

48 31

116

Darstellung: Matrix oder ListeKL/48FT/36BI/35 MZ/33

RB/28MZ/35AZ/35

AZ

BI

SP/31KL/48AZ/36FT

TR/116FT/48AZ/48KL

TR/128RB/54KO

BI/35AZ/33MZ

TR/128KO/54BI/28RB

FT/31SP

KO/128RB/98KL/116TR

AZ

BI

FT

KL

KO

MZ

RB

SP

TR

AZ

35

36

48

33

BI

35

35

28

FT

36

48

31

KL

48

48

116

KO

54

128

MZ

33

35

RB

28

54

98

SP

31

TR

116

128

98

Adjazenzliste

Adjazenzmatrix

35 Einfache Version

AZ

BI

FT

KL

KO

MZ

RB

SP

TR

AZ

35

36

48

33

BI

35

35

28

FT

36

48

31

KL

48

48

116

KO

54

128

MZ

33

35

RB

28

54

98

SP

31

TR

116

128

98

TR

KO

RB

BI

KL

AZ

MZ

FT

SP

128

98

54

28 35

3533

3648

48 31

116

Grundidee:

Die Adjazenzmatrix wird mit Hilfe einer zweidimensionalen Reihung dargestellt.

36 Einfache Version

type tKnoten = (A, B, F, K, O, M, R, S, T); tAdjMatrix = array [tKnoten, tKnoten] of real;

const graph: tAdjMatrix = ((-1, 35, 36, 48, -1, 33, -1, -1, -1), (35, -1, -1, -1, -1, 35, 28, -1, -1), ... (-1, -1, -1,116,128, -1, 98, -1, -1));

AZ

BI

FT

KL

KO

MZ

RB

SP

TR

AZ

35

36

48

33

BI

35

35

28

FT

36

48

31

KL

48

48

116

KO

54

128

MZ

33

35

RB

28

54

98

SP

31

TR

116

128

98

Grundidee:

Die Adjazenzmatrix wird mit Hilfe einer zweidimensionalen Reihung dargestellt.

37 Objektorientierte Version

Grundidee:

- Jeder Knoten ist ein Objekt.

- Jede Kante ist ein Objekt.

TR

KO

RB

BI

KL

AZ

MZ

FT

SP

128

98

54

28 35

3533

3648

48 31

116

KL/48FT/36BI/35 MZ/33

RB/28MZ/35AZ/35

AZ

BI

SP/31KL/48AZ/36FT

TR/116FT/48AZ/48KL

TR/128RB/54KO

BI/35AZ/33MZ

TR/128KO/54BI/28RB

FT/31SP

KO/128RB/98KL/116TR

38 Objektorientierte Version

KL/48FT/36BI/35 MZ/33

RB/28MZ/35AZ/35

AZ

BI

SP/31KL/48AZ/36FT

TR/116FT/48AZ/48KL

TR/128RB/54KO

BI/35AZ/33MZ

TR/128KO/54BI/28RB

FT/31SP

KO/128RB/98KL/116TR

TKnoten

- name: string- kanten: TList

+ create(n: string)+ fuegeHinzu(k: TKante)+ getName: string+ getKanten: TList

TGraph

- alleKnoten: TList

+ create+ neuerKnoten(n: string)+ neueKante(n1, n2: string; g: double)+ getAlleKnoten: TList

*

TKante

- zielKnoten: TKnoten- gewicht: double

+ create(k: TKnoten; g: double)+ getZielKnoten: TKnoten+ getGewicht: double

**

:TList

0

1

2

3

5

6

6

7

8

:TList

:TList

:TList

:TList

:TList

:TList

:TList

:TList

:TList

0 1 2 3

39 Zielsetzung

Ziel ist es, ein Programm zu entwickeln, mit dessen Hilfe man Graphen verwalten kann. Folgende Anforderungen soll das Programm erfüllen:

/1/ Der Benutzer kann die Knoten und Kanten eines (gewichteten) Graphen schrittweise eingeben.

/2/ Die aktuellen Knoten und Kanten eines Graphen werden (in einfacher Form) auf der Benutzungsoberfläche angezeigt.

/3/* Der Benutzer kann nachträglich auch Knoten und Kanten des eingegebenen Graphen löschen.

/4/* Man kann sich einen kürzesten Weg von einem eingegebenen Start- zu einem eingegebenen Zielknoten berechnen und anzeigen lassen.

...

40 Fertige Klasse nutzen

Häufig findet man zu Standardproblemen fertige Lösungen in Form implementierter Klassen.

Wir gehen im Folgenden davon aus, dass es eine (halb-) fertig implementierte Klasse TGraph gibt, deren Funktionalitäten wir direkt für unsere Zwecke nutzen können.

TKnoten



TGraph

- alleKnoten: TList


**

*

TKante



41 Aufgabe

Auf den folgenden Folien finden Sie eine Dokumentation zu den dargestellten Klassen. Schauen Sie sich diese Dokumentation zunächst genau an und nutzen Sie sie bei der weiteren Arbeit.

TKnoten



TGraph

- alleKnoten: TList


**

*

TKante



42 Dokumentation der Klasse TKnoten

Konstruktor create (n: string)nachher: Es ist ein Knoten mit dem Namensattributwert "name" erzeugt worden. Zudem ist ein Listenobjekt zur Verwaltung von Kanten erzeugt worden. Es gibt noch keine Kantenobjekte, die mit dieser Liste verwaltet werden.

Auftrag fuegeHinzu(k: TKante)nachher: Ein Kantenobjekt ist in die Liste zur Verwaltung der Kanten aufgenommen worden.

Anfrage getName: stringnachher: Die Anfrage liefert den Namen des Knotens.

Anfrage getKanten: TListnachher: Die Anfrage liefert die Liste der Kanten des Knotens. Hat der Knoten keine Kanten, wird der Wert "nil" zurückgeliefert.

Destruktor destroynachher: Der Knoten existiert nicht mehr. TKnoten



43 Dokumentation der Klasse TKante

Konstruktor create (k: TKnoten; g: double)nachher: Es ist eine gerichtete Kante mit dem Zielknoten / Nachbarknoten "k" und dem Gewicht "g" erzeugt worden.

Anfrage getZielKnoten: stringnachher: Die Anfrage liefert den Namen des Zielknotens.

Anfrage getGewicht: doublenachher: Die Anfrage liefert das Gewicht der Kante.

Destruktor destroynachher: Die Kante existiert nicht mehr.

TKante



44 Dokumentation der Klasse TGraph

Konstruktor create nachher: Es ist ein neues Graphobjekt erzeugt worden. Zudem ist ein Listenobjekt zur Verwaltung aller Knoten erzeugt worden. Es gibt noch keine Knotenobjekte, die mit dieser Liste verwaltet werden.

Auftrag neuerKnoten(n: string)nachher: Falls noch kein Knoten mit Namen "n" in der Liste aller Knoten vorkommt, so wird ein neues Knotenobjekt mit dem übergebenen Parameter als Namensattributwert erzeugt und in die Liste aller Knoten eingefügt. Ansonsten bleibt die Liste aller Knoten wie bisher.

Auftrag neueKante(n1, n2: string; g: double)nachher: Falls noch keine Kante von Knoten "n1" zu Knoten "n2" existiert, so wird ein neues Kantenobjekt erzeugt und in die Liste aller Kanten zum Knoten "n1" hinzugefügt.

Anfrage getAlleKnoten: TListnachher: Die Anfrage liefert die Liste aller Knoten des Graphen.

Destruktor destroynachher: Der Graph existiert nicht mehr.

TGraph

- alleKnoten: TList


45 Aufgabe

Ziel: einen Graphen aufbauen

Entwickeln Sie eine passende Benutzungsoberfläche.

Erzeugen Sie ein Objekt der Klasse TGraph. Benutzen Sie die von der Klasse TGraph bereit gestellten Methoden, um die Knoten und Kanten eines vorgegebenen Graphen zu erzeugen.

46 Aufgabe

Ziel: einen Graphen anzeigen

Erweitern Sie die Benutzungsoberfläche passend.

Benutzen Sie die von der Klasse TGraph bereit gestellten Methoden, um auf die Knoten und Kanten eines zuvor erzeugten Graphen zuzugreifen und die zugehörigen Informationen anzuzeigen. Beachten Sie, dass die von TGraph bereit gestellten Methoden Knoten bzw. Kanten als Listen zurückgeben. Informieren Sie sich (z. B. im Demoprogramm „Listen“), wie man auf die Objekte einer Liste zugreift und die verwalteten Daten anzeigt.

47 Aufgabe

Ziel: Knoten oder Kanten eines Graphen löschen

Die Klasse TGraph enthält noch keine Methoden, mit deren Hilfe man Knoten oder Kanten eines Graphen löschen kann. Ergänzen Sie passende Methoden und implementieren Sie diese.

48 Aufgabe

Ziel: Algorithmus von Dijkstra oder Moore implementieren

Erweitern Sie die Klasse TGraph um die Möglichkeit, kürzeste Wege mit dem Algorithmus von Dijkstra oder Abstände mit dem Algorithmus von Moore zu bestimmen (Achtung: etwas aufwendiger).

Sie können sich auch eine fertige Lösung zu einem der drei vorgestellten Probleme anschauen (z. B. Graph durchlaufen) und diese dann zu einer Lösung eines anderen Problems (z. B. Abstände bestimmen) umarbeiten.

49 Teil 4

Zusammenfassung

50 Standardlösungen

Warum das Rad neu erfinden? Oft ist es sinnvoll, fertige Lösungen zu nutzen, anstatt selbst nach Lösungen zu suchen. Im Unterricht bieten sich oft Situationen wie:- einen Standardalgorithmus erkunden und nutzen- eine vorgefertigte Klasse nutzen und ggf. erkunden und erweitern{Eingabe: Graph G; Startknoten s des Graphen}

für alle Knoten w setze dg(w) = ∞ setze dg(s) = 0 füge s in eine (zunächst leere) Datenstruktur D ein solange D nicht leer ist entnimm einen Knoten w mit minimalem dg(w) aus D für alle Kanten {w,u} falls dg(u) = ∞ füge u in D ein falls dg(u) > dg(w) + g({w,u}) setze dg(u) = dg(w)+g({w,u})

{Ausgabe: gewichteter Abstand dg(w) aller Knoten w vom Startknoten s}

TKnoten



TGraph

- alleKnoten: TList


**

*

TKante



51 Literaturhinweise

Folgende Materialien wurden hier benutzt:

U. Schöning: Ideen der Informatik. Oldenbourg Verlag 2002.

P. Gritzmann, R. Brandenburg: Das Geheimnis des kürzesten Weges. Springer 2002.

Mathe-Prisma: Graphenhttp://www.matheprisma.uni-wuppertal.de/Module/Graphen/index.htm

D. Jonietz: Graphen http://informatik.bildung-rp.de/fileadmin/user_upload/informatik.bildung-rp.de/Weiterbildung/pdf/WB-VIII-6-Graphen.pdf

Documents

Graphen und ihre Implementierung Klaus Becker 2007