FB Informatik
Prof. Dr. R.Nitsch
Programmieren 2
Future Car Projekt
Praktikum 6 - Graphen
- Speichern von Graphen
- Traversieren von Graphen
- Kürzeste Wege
Reiner Nitsch
 reiner.nitsch@h-da.de
Darstellung von Graphen als Array von Listen
• Grundlagen zu Graphen (siehe
Vorlesung Mathematik 1)
Array von
Adjazenzlisten
1
4
2
5
3
6
Ungerichteter Graph G(V,E)
V: Knotenmenge
E: Kantenmenge
1
2
4 
2
5
4
3
5
6 
4
1
2
5 
5
4
3
2 
6
3
6
1
2
2
5 
3
5
6
4
2 
Gerichteter Graph
5
4 
6
6 
1
4
2
5
09.10.2008
3
FB Informatik
Prof. Dr. R.Nitsch
4 
6 
Projekt FutureCar
Adjazenzlisten
1 
Die mit Knoten 5 direkt
verbundenen Nachbarknoten
(= Kantenmenge E5 )
Adjazenzlisten erlauben Antwort auf
Fragen zu Graphen G wie z.B.
• Wieviele Kanten enden an vi?
• Welche Nachbarn vj hat vi?
• Existiert Kante E=(vi,vj)?  O(|Ei|)
Gewichteter Graph: Gewicht als zusätzliche Info der Listenelemente
Speicherbedarf?  proportional zur
Anzahl Knoten plus Anzahl Kanten 
O(|V|+|E|)
2
Darstellung von Graphen mit Adjazenzmatrix
Adjazenzmatrix a mit Elementen aij
aij = 1 wenn Kante E=(vi,vj) in G
enthalten, sonst aij=0
1
2
3
4
5
6
Ungerichteter Graph G(V,E)
1
2
3
4
5
6
Gerichteter Graph G(V,E)
09.10.2008
1
2
3
i 4
5
6
1
0
1
0
1
0
0
2
1
0
0
1
1
0
j

3 4
0 1
0 1
0 0
0 0
1 1
1 0
5
0
1
1
1
0
0
6
0
0
1
0
0
1
 aij = aji (symmetrisch)
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
0
0
0
1
0
0
1
FB Informatik
Prof. Dr. R.Nitsch
Adjazenzlisten erlauben Antwort
auf Fragen zu Graphen G wie
z.B.
• Wieviele Kanten enden an vi?
• Welche Nachbarn vj hat vi?
• Existiert Kante E=(vi,vj) mit
Zeitkomplexität O(1)
Speicherbedarf? O(|V|2)
 ungünstig wenn G wenige
Kanten hat
Gewichteter Graph: Gewicht an
Stelle von '1' in Matrix
eintragen
 aij ≠ aji (unsymmetrisch)
Projekt FutureCar
3
Anwendungsbeispiel - FutureCar-Projekt
FB Informatik
Prof. Dr. R.Nitsch
• Die FutureCar-Anwendung ist ein TestUnit für AutopilotAlgorithmen zur autonomen Steuerung von Fahrzeugen.
• Das TestUnit besteht aus einem virtuellen
Straßenlabyrinth (FCWelt, s. Abb.) in dem sich viele
virtuelle Fahrzeuge (FutureCars) gesteuert durch ihren
individuellen Autopiloten unfallfrei bewegen müssen.
Allgemeine Vorgaben/Einschränkungen:
• Die FCWelt soll auf einem zeichenorientierten Display
darstellbar sein.
– Dazu muss sie rechteckig und in virtuelle Parzellen (s.
Abbildung) unterteilt sein.
– Jede Parzelle symbolisiert ein FutureCar, ein Haus
oder einen Teil der Straße.
– Alle Straßen sind zweispurig und verlaufen senkrecht
zueinander. Sie werden begrenzt durch Häuser.
– Jedes FutureCar verfügt über einen Scanner, zum
Abtasten seiner unmittelbaren Umgebung
– Für Navigationsaufgaben ist das Straßennetz in Form
von Adjazenzlisten darzustellen.
09.10.2008
Projekt FutureCar
4
Adjazenzliste des Graphen der FutureCar World
FB Informatik
Prof. Dr. R.Nitsch
Rasterkarte (Grid) von FC-City
# # # #
#
1
4
#
#
#
x
y

0,0
1,0
2,0
3,0
0,1
1,1
2,1
3,1
0,2
1,2
2,2
3,2
0,3
1,3
2,3
3,3
Rasterkarte von FC-City
mit XY-Koordinaten:
Jede Parzelle ist ein Knoten
1,1
1,2 
2,1
1,1 
3,1
2,1
1,2
1,3
2,2
3,2
3,2
3,1
3,2 
4,2 
2
Adjazenzlisten
5
Graph zur Modellierung der
Erreichbarkeitsbeziehungen
zwischen den Zellen
der Rasterkarte
3
1 1; 1 2;
2 1; 1 1;
3 1; 2 1; 3 2;
1 2; 1 3;
2 2; 3 2;
3 2; 3 1; 4 2;
Adjazenzlisten als
Textsequenz (ohne
Kantengewichte)
09.10.2008
Projekt FutureCar
5
Dateiformat des Graphen
FB Informatik
Prof. Dr. R.Nitsch
Rasterkarte (Grid) von FC-City
# # # #
#
1
#
#
#
x
y

0,0
1,0
2,0
3,0
0,1
1,1
2,1
3,1
Rasterkarte von FC-City
mit XY-Koordinaten:
Jede Parzelle ist ein Knoten
2
0,2
1,2
2,2
3,2
0,3
1,3
2,3
3,3
Graph zur Modellierung der
Erreichbarkeitsbeziehungen
zwischen den Zellen
der Rasterkarte
3
09.10.2008
Projekt FutureCar
// Knotenliste
(1,1)
(1,2)
Knoten und Kanten
(1,3)
im Dateiformat
(2,1)
(2,2)
(2,3)
(3,1)
(3,2)
…,…
// Kantenliste
// <von>;<nach>;<Gewicht>;
(1,1);(1,2);1
(1,2);(1,3);
(1,3);(2,3);30;
(2,1);(1,1);1;
(2,2);(3,2);1;
(2,3);(2,2);1;
(2,3);(1,3);30;
(3,1);(2,1);1;
(3,1);(3,2);30;
(3,2);(3,1);30;
…,…
6
Implementierung mit indexbasierten Arrays
Location
+ x,y:int
Node
FB Informatik
Prof. Dr. R.Nitsch
1,1
1,2 
2,1
1,1 
3,1
2,1
3,2 
1,2
2,2
1,3 
Graph
- nodes:vector<Node>
2,2
2,1
3,2 
+ Konstruktor
+…
3,2
3,1
4,2 
+ loc
2,2
+ pfirst:ListElem* 2,1
+ Konstruktor:
1..N
1
3,2
ListElem
+ loc:Location
+ pnext:ListElem*
Adjazenzlisten
Problem
Um z.B. auf die Adjazenzliste des Knotens K=(3,1) zuzugreifen, braucht man seinen
Index. Diesen findet man in linearen Datentypen (Liste, Array) nur durch lineare
Suche nach dem Schlüsselwert (3,1). Lineare Suche hat die Kosten O(N).
Idee
Wenn man den Index von K direkt aus seinem Schlüsselwert (3,1) berechnen könnte,
wäre ein Suchverfahren mit konstanten Kosten, d.h. O(1) gefunden!
Vorschläge?
09.10.2008
Projekt FutureCar
7
Traversieren von Graphen
FB Informatik
Prof. Dr. R.Nitsch
• Als Traversieren bezeichnet man das systematische Besuchen aller Knoten und das
Durchlaufen jeder Kante eines Graphen.
• Algorithmen zum Traversieren eines Graphen dienen als Basis für viele andere
grundlegende Algorithmen zur Verarbeitung von Graphen
• Man unterscheidet zwischen
– Breitentraversierung (breadth-first search, BFS): Die Knoten werden, geordnet
nach der "Entfernung" von einem Startknoten, durchlaufen
• zuerst alle Knoten mit 1 Kantenlänge Abstand vom Startknoten
• danach alle diejenigen Knoten mit Abstand 2,
• danach die mit Abstand 3, usw.
– Tiefentraversierung (depth-first search, DFS): Dieser Algorithmus erhöht
immer zuerst die Distanz vom Startknoten, bevor er in die Breite geht und
Nachbarknoten mit gleicher Distanz besucht (meist rekursiv implementiert)
• Bereits besuchte Knoten müssen markiert werden,
Node
weil sich die Algorithmen sonst in den Kreisen des
+ loc:Location
Graphen verlieren.
Markierung
+ adjList
+ visited:bool
+ Konstruktor:
09.10.2008
Projekt FutureCar
8
Tiefentraversierung (Rekursiv)
FB Informatik
Prof. Dr. R.Nitsch
• Rekursiver Algorithmus (in Pseudocode), der ausgehend von einem unmarkierten
Knoten vi, alle anderen Knoten vj, j!=i eines Graphen G besucht
Funktion: traverse-dfs(v)
Zweck: Tiefensuche in einem Graphen
Parameter v: Knoten bei dem die Suche beginnt
PRE: --POST: Alle Knoten, die von v erreichbar sind,
sind gefunden.
Node
- loc:Location
- adjList
- visited:bool
+ Konstruktor:
procedure traverse-dfs(v)
visited(v) := true
Markiere v als besucht
vnext := adjList[v]
Bestimme einen Nachbarknoten von v und nenne
diesen vnext
WHILE exist(vnext)
WHILE(vnext existiert
AND NOT visited(vnext)
UND noch nicht besucht ist)
beginne weitere Tiefensuche bei vnext
traverse-dfs(vnext)
Wieder zurück,
bestimme weiteren Nachbarknoten von v
vnext := succ(vnext)
und nenne diesen wieder vnext
END WHILE
END WHILE
Pseudocode (verbal)
Pseudocode (mnemonisch)
09.10.2008
Projekt FutureCar
9
Beispiel zur (rekursiven) Tiefentraversierung
procedure traverse-dfs(v)
visited(v) := true
vnext := adjList[v]
WHILE exist(vnext)
AND NOT visited(vnext)
traverse-dfs(vnext)
vnext := succ(vnext)
END WHILE
FB Informatik
Prof. Dr. R.Nitsch
Adjazenzlisten
von Seite 2
Startknoten
2
3
1
2
3
1
2
3
4
5
6
4
5
6
4
5
6
1
2
3
4
09.10.2008
2
5
2
4 
2
5
4
3
5
6 
4
1
2
5 
5
4
3
2 
6
3
6
1 
Komplexität: O(|V|+|E|)
1
1
1
3
6
4
5
6
Projekt FutureCar
Alle Knoten und
Kanten besucht!
10
Tiefentraversierung (Iterativ)
FB Informatik
Prof. Dr. R.Nitsch
• Iterativer Algorithmus mit einem Stack, der ausgehend von einer unmarkierten Ecke
vi, alle anderen Knoten vj, j!=i eines Graphen G besucht
PRE: ---
POST: Alle Ecken, die von v erreichbar sind, sind markiert.
procedure traverse-dfs(v)
s := empty-stack
visited(v) := true
push(s,v)
WHILE NOT empty(s) DO {
v := top(s)
vnext := adjList[v]
// s ist ein lokaler Stack
// markiere v als besucht
// lege v auf den Stack s
// hole oberstes Element aus Stack s
// hole ersten Nachbarknoten
WHILE exist(vnext) AND visited(vnext) DO // schon besucht?
vnext := succ(vnext)
// Ja! Dann eben den Nächsten
END WHILE
IF( exist(vnext) ) ) THEN
// Noch einen Unbesuchten gefunden?
visit(vnext)
// diesen besuchen (und bearbeiten),
visited(vnext) := true
// als "besucht" markieren und
push(s,vnext)
// Erst mal auf den Stack damit ...
ELSE DO
pop(s)
END IF
END WHILE
// Erledigt! Alle Nachbarn von v besucht
}
09.10.2008
Projekt FutureCar
… und hier
schon wieder
runter!
11
Breitentraversierung
FB Informatik
Prof. Dr. R.Nitsch
• Iterativer Algorithmus, der alle Knoten eines zusammenhängenden Graphen geordnet nach der
Entfernung vom Startknoten s durchläuft.
– Zuerst werden alle vom Startknoten s über 1 Kante erreichbaren Knoten besucht
– Danach alle über mindestens 2 Kanten erreichbaren Knoten, usw.
– Entsteht formal aus Tiefentraversierung, wenn man den Stack durch eine Queue ersetzt.
PRE:
--Post:
Alle Knoten, die von s erreichbar sind, sind markiert, also besucht worden
procedure bfs_node(s)
q := empty-queue
// Definition einer leeren lokalen Queue q
visited(s) := true
// Startknoten s als "besucht" markieren
enqueue(q,s)
WHILE NOT empty(q) DO
v := front(q)
// vordersten Knoten in q lesen
vnext := adjList[v]
// hole ersten Nachbarknoten
WHILE exist(vnext) AND visited(vnext) DO
// schon besucht?
vnext := succ(vnext)
// Ja! Dann eben den Nächsten
END WHILE
IF exist(vnext) THEN
// Noch einen Unbesuchten gefunden?
visit(vnext)
// diesen besuchen (und bearbeiten),
visited(vnext) := true
// als "besucht" markieren und
enqueue(q,vnext)
// erst mal in queue einreihen, wo sie bis zur
// Bearbeitung ihrer Nachbarknoten warten
ELSE DO
dequeue(q)
// Erledigt! Alle Nachbarn von v mit gleichem
END IF
// Abstand vom Startknoten wurden besucht.
12
Projekt FutureCar
END09.10.2008
WHLE
procedure bfs_node(s)
q := empty-queue
visited(s) := true
enqueue(q,s)
WHILE NOT empty(q) DO
v := front(q)
vnext := adj[v]
WHILE exist(vnext) AND visited(vnext) DO
vnext := succ(vnext) END WHILE
IF exist(vnext) THEN
visit(vnext)
visited(vnext) := true
enqueue(q,vnext)
ELSE
dequeue(q)
END IF
2
t:
END WHILE
Beispiel zur Breitentraversierung
FB Informatik
Prof. Dr. R.Nitsch
Adjazenzlisten
von Seite 2
1
2
4 
2
5
4
3
5
6 
4
1
2
5 
5
4
3
2 
6
3
6
1 
Queue
5
4
1
3
6
Startknoten
1
2
3
1
2
3
1
2
3
4
5
6
4
5
6
4
5
6
1
2
3
1
2
3
4
09.10.2008
5
6
4
5
6
Projekt FutureCar
Jetzt sind alle
Knoten mit Distanz
"1Kante" zum
Startknoten besucht
Alle Knoten und
Kanten besucht!
13
Kürzeste Wege mittels Breitensuche
FB Informatik
Prof. Dr. R.Nitsch
• Gesucht ist eine Verbindung (Pfad) zwischen 2 Knoten:
– Tiefensuche liefert eine entsprechende Kantenfolge, wenn es eine gibt (aber nicht
unbedingt die Kürzeste).
– Breitensuche liefert garantiert die Kürzeste.
• Aufgabe
Mit Hilfe eines Breitensuchverfahrens soll der kürzeste Weg in einem ungewichteten
Graphen G vom Startpunkt s zum Zielknoten d gefunden werden, der über die
geringste Anzahl von Kanten verläuft. Dabei wird der Weg so codiert, dass man ihn
hinterher rekonstruieren kann.
• Lösung
– Die Breitentraversierung durchläuft alle Knoten geordnet nach der Kantendistanz
zu s.
– Der Vorgängerknoten, von dem ausgehend der Knoten v betreten wird, verbindet
somit v auf dem kürzesten Wege mit s (keine Kantengewichte!).
– Im Bearbeitungsschritt merkt sich Knoten v daher seinen Vorgängerknoten
– Nachdem Knoten d betreten wurde und dieser sich seinen Vorgängerknoten
gemerkt hat, ist die Suche beendet.
– Der kürzeste Weg, der d mit s verbindet, ergibt sich nun, indem man, beginnend
bei d, die Folge der Vorgängerknoten rekonstruiert.
– Rückwärts gelesen (std::reverse) ergibt diese Folge den gesuchten kürzesten
Weg.
14
09.10.2008
Projekt FutureCar
Breitensuche des Knotens d ausgehend vom Startknoten s
PRE:
POST:
FB Informatik
21.12.12 Prof. Dr. R.Nitsch
exist(s), exist(d)
Alle Knoten, die von v erreichbar sind, sind markiert, also besucht worden
FUNCTION bf_search(s,d)
t := empty-queue
visited(s) := true
pred(s) := nil
enqueue(t,s)
Ergänzungen zum vorherigen Algorithmus sind ROT markiert
// Definition einer leeren lokalen Queue
// Starknoten v als "besucht" markieren
// s kennt seinen Vorgänger noch nicht
Verweis auf Vorgängerknoten
Node
- loc:Location
- adjList
- pred
- visited:bool
WHILE NOT empty(t) AND front(t)!=d DO // Abbruch der Suche wenn d besucht
+ Konstruktor:
v := front(t)
// vordersten Knoten in t lesen
vnext := adj[v]
// hole ersten Nachbarknoten
WHILE exist(vnext) AND visited(vnext) DO
vnext := succ(vnext)
// Bereits besuchte Knoten überspringen
END WHILE
IF vnext != nil THEN
// Solange unbesuchte Nachbarknoten zu v existieren
visit(vnext)
// diese besuchen (und bearbeiten),
pred(v_next) := v
// Vorgänger merken (besuchen & bearbeiten)
visited(vnext) := true
// als solche markieren und
enqueue(t,vnext)
// in queue einfügen, wo sie bis zur Bearbeitung
// ihrer Nachbarknoten warten
ELSE DO
dequeue(t)
// entferne vorderstes Element aus t
END IF
// Alle Nachbarn dieses Knotens sind besucht
IF empty(t) THEN
{ kein Pfad von s nach d }
09.10.2008
Projekt FutureCar
15
Wegesuche in gewichtetem Graphen
FB Informatik
Prof. Dr. R.Nitsch
Aufgaben
– Von einem Knoten s aus die kürzesten Pfade zu allen anderen Knoten des Graphen
finden: Lösung mit single-source shortest path (SSSP) Algorithmen
– Für alle Paare von Knoten die kürzesten Pfade finden: Lösung mit all-pair
shortest path (APSP) Algorithmen
• Kürzeste Wege
– im ungewichteten Graph: Pfad mit geringster Kantenzahl
– im gewichteten Graph: Pfad mit geringstem Gesamtgewicht
• Kürzeste Wege sind nicht eindeutig
– wenn 2 Wege das gleiche Gesamtgewicht haben
• Kürzeste Wege existieren dann nicht
– wenn gar kein Weg zwischen 2 Knoten existiert
– falls der Graph Zyklen mit negativem Gesamtgewicht hat (jeder Durchlauf
verringert das Gewicht des Pfades.
• Wichtige Algorithmen:
– Dijkstra-Algorithmus (SSSP): für Graphen mit Kantengewichten  0
– Belman-Ford-Algorithmus: Für Graphen mit negativen Gewichten aber ohne
negative Zyklen (= Zyklen mit Kantensumme< 0).
09.10.2008
Projekt FutureCar
16
Dijkstra Algorithmus
FB Informatik
Prof. Dr. R.Nitsch
• Liefert für alle Knoten eines Graphen G die kürzesten Pfade zu einem Startknoten s
• Wirkungsweise
algorithm dijkstra(G,s)
Node
– Zusätzlich zu seiner Adjazenzliste erhält
Eingabe: Graph G, Startknoten s
+ loc:Location
jeder Knoten v die Angabe
FOR EACH Knoten v aus V(G) DO
+ adjList
d2s[v]=
• zur minimalen Distanz d2s[v] von v zum
+ pred
pred[v]=nil
Startnoten s
+ d2s:float
OD
• des Vorgängerknotens pred[v] auf dem
d2s[s]=0 // Startknoten erhält höchste
Priorität
+ Konstruktor:
kürzesten Weg zum Startknoten
PQ:=V
– Einfügen aller Knoten in eine Priorityqueue PQ
WHILE NOT empty(PQ) DO
– Mit jedem Durchlauf wird der Knoten mit
vmin = dequeueMin(PQ)
der bis dahin geringsten Distanz zu s aus einer
// Für vmin ist der kürzeste Weg gefunden
PriorityQueue PQ entnommen (vmin ) und
FOR EACH vnext OF vmin DO
abschließend wie folgt bearbeitet:
dneu:=d(vmin)+w(vmin,vnext)
• die Distanz dneu der über vmin zu all seinen
Nachbarknoten führenden Wege wird ermittelt wobei w(vmin,vnext) das Gewicht der
Kante vmin->vnext ist.
IF dneu<d(vnext) DO
• falls die bisher für vnext notierte Distanz
d(vnext):=dneu
größer als dneu ist, wird diese
pred:=vmin
aktualisiert und vmin als neuer
FI
Vorgängerknoten eingetragen
OD
17
09.10.2008
Projekt FutureCarOD
Dijkstra-Algorithmus - Eigenschaften
FB Informatik
Prof. Dr. R.Nitsch
• Mit jeder Iteration wird ein kürzester Pfad ermittelt und der jeweilige Zielknoten
aus der Priorityqueue entfernt.
• Nach |V| Iterationen sind für alle Knoten die kürzesten Pfade zum Startknoten
bekannt.
09.10.2008
Projekt FutureCar
18

Graph