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?
10 Klassische Graphenprobleme
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
11 Klassische Graphenprobleme
Euler-Weg / Euler-Kreis:Gibt es einen (geschlossenen) Weg, der jede Kante genau einmal besucht?
Königsberger Brückenproblem Haus des Nikolaus
12 Klassische Graphenprobleme
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
13 Klassische Graphenprobleme
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
14 Klassische Graphenprobleme
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
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 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
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
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
{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 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}
Quelle: http://www.matheprisma.uni-wuppertal.de/Module/Graphen/index.htm
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
Vorbereitungsschritt
Wiederholungsschritt
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
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
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
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
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
{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}
Quelle: http://www.matheprisma.uni-wuppertal.de/Module/Graphen/index.htm
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})
Vorbereitungsschritt
Wiederholungsschritt
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
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
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
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})
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
- 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
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
- 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
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
- name: string- kanten: TList
+ create(n: string)+ fuegeHinzu(k: TKante)+ getName: string+ getKanten: TList
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
- zielKnoten: TKnoten- gewicht: double
+ create(k: TKnoten; g: double)+ getZielKnoten: TKnoten+ getGewicht: double
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
+ create+ neuerKnoten(n: string)+ neueKante(n1, n2: string; g: double)+ getAlleKnoten: 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
- 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
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