Transcript
Syntax und Semantik Java: Der Einstieg Imperative Programmierung in Java Algorithmen zur exakten Suche in Texten Objektori
Algorithmen und Datenstrukturen II Alexander Sczyrba AG Praktische Informatik Technische Fakult¨ at Universit¨ at Bielefeld
Vorlesung Sommer 2008
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Teil IX Graphen
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Anwendungen von Graphen Um einen Eindruck von der Vielfalt der Einsatzm¨ oglichkeiten von Graphen und Graphalgorithmen zu bekommen, wollen wir einige Beispiele betrachten: Karten Wenn wir eine Reise planen, wollen wir Fragen beantworten wie: Was ist der k¨ urzeste Weg von Bielefeld nach M¨ unchen? Was der schnellste Weg? Um diese Fragen beantworten zu k¨onnen, ben¨otigen wir Informationen u ¨ber Verbindungen (Reiserouten) zwischen Objekten (St¨adten). Hypertexts Das ganze Web ist ein Graph: Dokumente enthalten Referenzen (Links) auf andere Dokumente, durch die wir navigieren. Graphalgorithmen sind essentielle Komponenten der Suchmaschinen, die uns Informationen im Web finden lassen. Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Anwendungen von Graphen
Schaltkreise F¨ ur elektrische Schaltungen sind wir an kreuzungsfreien Chip-Layouts interessiert und m¨ ussen Kurzschl¨ usse vermeiden. Zeitpl¨ane Die Erledigung einiger Aufgaben h¨angt evtl. von der Erledigung anderer ab. Diese Abh¨angigkeiten k¨onnen als Verbindungen von Aufgaben modelliert werden. Ein klassisches scheduling Problem w¨are dann: Wie arbeiten wir die Aufgaben unter den gegeben Voraussetzungen am schnellsten ab?
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Anwendungen von Graphen
Netzwerke Computernetzwerke bestehen aus untereinander verbundenen Einheiten, die Nachrichten senden, empfangen und weiterleiten. Wir sind nicht nur daran interessiert, welchen Weg eine Nachricht von einem Ort zum anderen nehmen muss. Genauso will man sicherstellen, dass die Konnektivit¨at aller Orte auch dann gew¨ahleistet ist, wenn sich das Netzwerk ¨andert (Ausfallsicherheit). Genauso muss der Datenfluss sichergestellt sein, so dass das Netzwerk nicht ’verstopft’.
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Terminologie
V : Menge von Knoten (auch vertices oder nodes) E : Menge von Kanten (edges) G : Graph G = (V , E )
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Terminologie
Definition Ein Graph G = (V , E ) besteht aus einer Menge von Knoten V (auch vertices oder nodes) und einer Menge von Kanten E (edges). Jede Kante ist ein Paar (v , w ) ∈ V , das Paare von Knoten verbindet. Wir beschr¨anken uns im Folgenden auf Graphen, die keine doppelten (oder parallele) Kanten besitzen. (Graphen, die doppelte Kanten enthalten, nennt man Multigraphen.)
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Gewichtete Graphen
Definition Ein gewichteter Graph (weighted graph) ist ein Graph, in dem Kanten mit Gewichten versehen sind. Gewichtete Graphen enthalten somit zus¨atzliche Attribute, in denen z.B. die L¨ange einer Kante (bei der Modellierung eines Straßennetzes) repr¨asentiert werden k¨onnen.
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Repr¨asentation von Bahnverbindungen als Graph HH
160
H
110 115
285
B
293
BI
DO
350
220 585
F
630
210
S 230
M
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Typische Fragen
Gibt es eine direkte Verbindung zwischen Stadt BI und M? Welches ist der k¨ urzeste Weg von BI nach S? Welches ist der k¨ urzeste Weg, der in Stadt F startet und alle St¨adte einmal besucht?
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Gerichtete Graphen
Definition Ein gerichteter Graph (directed graph, digraph) ist ein Graph, in dem jede Kante eine Richtung hat. F¨ ur u, v ∈ V ist dann (u, v ) 6= (v , u). In gerichteten Graphen k¨onnen zwei Knoten durch zwei Kanten verbunden sein, allerdings nur durch je eine Kante in jede Richtung.
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Teilgraphen
Definition Ein Teilgraph (subgraph) von (V , E ) ist ein Paar (V 0 , E 0 ), mit V 0 ⊂ V und E 0 = {(u, v )|(u, v ) ∈ E : u ∈ V 0 , v ∈ V 0 }.
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Verbundene Graphen
Definition Ein Graph heißt verbunden (connected), wenn jeder Knoten von jedem anderen Knoten aus erreicht werden kann. Ein Graph, der nicht verbunden ist, besteht aus einer Menge von Zusammenhangskomponenten (connected components), die maximal verbundene Teilgraphen sind.
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Nachbarn
Definition Zwei Knoten u, v ∈ V mit u 6= v heißen benachbart (adjacent), wenn (u, v ) ∈ E oder (v , u) ∈ E .
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Grad Definition Bei der Bestimmung des Grads (degree) eines Knotens muss man zwischen ungerichteten und gerichteten Graphen unterscheiden: ungerichtete Graphen: Der Grad eines Knotens ist die Zahl seiner Nachbarn. gerichtete Graphen: Der Eingangsgrad (in-degree) eines Knotens v ∈ V ist die Zahl der Kanten (u, v ) ∈ E . Der Ausgangsgrad (out-degree) eines Knotens v ∈ V ist die Zahl der Kanten (v , u) ∈ E . Der Grad ist die Summe von Eingangs- und Ausgangsgrad.
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Pfad
Definition Ein Pfad (path) von u nach v ist einen Folge von Knoten u1 , u2 , . . . , uk , so daß u1 = u und uk = v und (ui , ui+1 ) ∈ E f¨ ur alle 1 ≤ i < k.
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Zyklus
Definition Ein Zyklus (cycle) ist ein Pfad, in dem Start- und Endknoten identisch sind.
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
B¨aume
Definition Auch B¨aume sind spezielle Graphen: Ein Baum (tree) ist ein ungerichteter, verbundener Graph ohne Zyklen (genauer: ohne Kreise, also Zyklen, in denen nur Anfangs- und Endpunkt identisch sind). Eine Menge von B¨aumen heißt Wald (forest). Ein Spannbaum (spanning tree) eines verbundenen Graphen (V , E ) ist ein Teilgraph, der alle Knoten V enth¨alt und ein Baum ist.
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Repr¨asentation von Graphen
Um Graphen darzustellen gibt es zwei Standardm¨oglichkeiten: Adjazenzlisten Adjazenzmatrizen Beide k¨ onnen sowohl f¨ ur gerichtete als auch ungerichtete Graphen verwendet werden.
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Repr¨asentation von Graphen
Bei d¨ unn besetzten (sparse) Graphen, bei denen die Anzahl der Kanten |E | viel kleiner als |V |2 ist, liefern Adjazenzlisten eine kompakte Darstellung. Die Repr¨asentation durch Adjazenzmatrizen wird vorgezogen, wenn der Graph dicht besetzt (dense) ist (d.h. wenn |E | nahe an |V |2 liegt, oder wenn ein Algorithmus m¨oglichst schnell hearusfinden muss, ob zwei Knoten verbunden sind.
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Adjazenzlisten und Adjazenzmatrizen
1
1
2
5
2
1
5
3
2
4
4
2
5
5
4
1
1
2
3
4
5
1
0
1
0
0
1
2
1
0
1
1
1
3
0
1
0
1
0
3
4
0
1
1
0
1
2
5
1
1
0
1
0
2 3
5
3
4
4
(a)
Alexander Sczyrba A&D II, Vorlesung 2008
(b)
(c)
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Adjazenzmatrizen und Adjazenzmatrizen
1
2
4
5
(a)
Alexander Sczyrba A&D II, Vorlesung 2008
1
2
3
4
5
6
1
0
1
0
1
0
0
2
0
0
0
0
1
0
3
0
0
0
0
1
1
2
4
0
1
0
0
0
0
5
4
5
0
0
0
1
0
0
6
6
6
0
0
0
0
0
1
1
2
2
5
3
6
4
4
3
6
5
(b)
(c)
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Adjazenzmatrizen
ben¨otigt O(V 2 ) Platz alle benachbarten Knoten von u k¨onnen in Θ(V ) bestimmt werden um zu u ufen, ob (u, v ) ∈ E gilt, wird O(1) Zeit ben¨otigt ¨berpr¨ gewichtete Graphen k¨onnen dargstellt werden, indem man in der Matrix Gewichte statt Bits speichert
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Adjazenzlisten
ben¨otigt Θ(V + E ) Platz alle benachbarten Knoten von u k¨onnen in Θ(degree(u)) bestimmt werden um zu u ufen, ob (u, v ) ∈ E gilt, wird O(degree(u)) Zeit ¨berpr¨ ben¨otigt
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
ADT Graph
Wir wollen nun einen abstrakten Datentypen f¨ ur Graphen beschreiben, der als Java-Interface definiert wird. Dieses sehr einfach gehaltene Interface gen¨ ugt, um die in den n¨achsten Abschnitten beschriebenen Algorithmen zu implementieren. Der Graph Konstruktor bekommt zwei Parameter: einen Integer-Wert f¨ ur die Anzahl der Knoten im Graphen und einen Boolean, der angibt, ob der Graph gerichtet ist oder nicht. Die Operationen beschr¨anken sich zun¨achst auf:
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Operationen ADT Graph
numOfV() gibt die Anzahl der Knoten zur¨ uck numOfE() gibt die Anzahl der Kanten zur¨ uck directed() gibt an, ob der Graph gerichtet ist insert(e) f¨ ugt eine Kante in den Graphen ein remove(e) l¨oscht einen Kante aus dem Graphen edge(v,w) u uft, ob es eine Kante zwischen Knoten v und ¨berpr¨ w gibt getAdjList(v) stellt einen Iterator zur Verf¨ ugung, der alle benachbarten Knoten von v aufz¨ahlt
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
ADT Graph - Java interface (I) Beispiel public interface Graph { Graph(int numOfVertices, boolean directed); int numOfV(); int numOfE(); boolean directed(); void insert(Edge e); void remove(Edge e); boolean edge(int v, int w); AdjList getAdjList(int v); }
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
ADT Graph - Java interface (II) Beispiel public interface AdjList { int begin(); int next(); boolean end(); } public class Edge { int v; int w; Edge(int v, int w) { this.v = v; this.w = w; } } Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Breitensuche BFS(G , s) 1 for each vertex u ∈ V [G ] − {s} 2 do color [u] ← WHITE 3 d[u] ← ∞ 4 π[u] ← NIL 5 color [s] ← GRAY 6 d[s] ← 0 7 π[s] ← NIL 8 Q←∅ 9 ENQUEUE(Q, s) 10 while Q 6= ∅ 11 do u ← DEQUEUE(Q) 12 for each v ∈ Adj[u] 13 do if color [v ] = WHITE 14 then color [v ] ← GRAY 15 d[v ] ← d[u] + 1 16 π[v ] ← u 17 ENQUEUE(Q, v ) 18 color [u] ← BLACK Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Tiefensuche DFS(G ) 1 for each vertex u ∈ V [G ] 2 do color [u] ← WHITE 3 π[u] ← NIL 4 time ← 0 5 for each vertex u ∈ V [G ] 6 do if color [u] = WHITE 7 then DFS-VISIT(u) DFS-VISIT(u) 1 color [u] ← GRAY B White vertex u has just been discovered. 2 time ← time + 1 3 d[u] ← time 4 for each v ∈ Adj[u] B Explore edge (u, v ). 5 do if color [v ] = WHITE 6 then π[v ] ← u 7 DFS-VISIT(v ) 8 color [u] ← BLACK B Blacken u; it is finished. 9 f [u] ← time ← time + 1 Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Topologisches Sortieren (I) 11/16
socks
undershorts
17/18 watch
(a)
12/15
6/7
pants
shoes shirt
1/8
tie
2/5
A&D II, Vorlesung 2008
13/14
belt
jacket
Alexander Sczyrba
9/10
3/4
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Topologisches Sortieren (I) 11/16
socks
undershorts
17/18 watch
(a)
pants
12/15
6/7
shoes shirt
1/8
tie
2/5
13/14
belt
jacket
(b)
9/10
3/4
socks
undershorts
pants
shoes
watch
shirt
belt
tie
jacket
17/18
11/16
12/15
13/14
9/10
1/8
6/7
2/5
3/4
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
Anwendungen von Graphen Repr¨ asentation von Graphen ADT Graph Breitensuche Tiefensuche Topologisches Sortieren Topolo
Topologisches Sortieren (II)
TOPOLOGICAL-SORT(G ) 1 call DFS(G ) to compute finishing times f [v ] for each vertex v 2 as each vertex is finished, insert it into the front of a linked list 3 return the linked list of vertices
Alexander Sczyrba A&D II, Vorlesung 2008
Universit¨ at Bielefeld
