CS计算机代考程序代写 algorithm hadoop ER Programmierung

Programmierung
Graphen
Michael Goedicke
michael.goedicke@paluno.uni-due.de auf der Basis von Folien von V Gruhn

Einführung: Graphen
▪ Listen dienen zur sequentiellen Speicherung von Daten: Jeder Knoten (außer dem letzten) hat genau einen Nachfolger.
▪ Beispiel: Medienliste einer Bibliothek
▪ Bäume dienen zur hierarchischen Speicherung von Daten: Jeder Knoten (außer den Blättern) kann mehrere Söhne haben, die wiederum Wurzeln von Unterbäumen sein können.
▪ Beispiel: Verzeichnisstruktur eines Dateisystems
▪ Graphen dienen zur Speicherung von Daten, die in beliebigen Beziehungen zueinander stehen können, ohne dass bestimmte Knoten eine ausgezeichnete Rolle spielen.
▪ Beispiel: Straßenverbindungen in einem Navigationssystem
M. Goedicke – Programmierung WiSe 2020/2021
2

Grundeigenschaften von Graphen
▪ Nicht nur die Knoten eines Graphen, sondern auch die Kanten zwischen ihnen können Informationen tragen. In diesem Fall spricht man von attributierten Graphen.
▪ Beispiel: Entfernungen zwischen Orten
▪ Gilt eine Beziehung zwischen zwei Knoten in beide Richtungen, so verwendet man ungerichtete Kanten. Gilt die Beziehung nur in eine Richtung, so verwendet man gerichtete Kanten.
▪ Beispiel: Verbindung zwischen Orten über normale Straße oder Einbahnstraße
▪ I.d.R. sind entweder alle Kanten gerichtet oder alle ungerichtet, daher spricht man von gerichteten bzw. ungerichteten Graphen.
M. Goedicke – Programmierung WiSe 2020/2021
3

Definition Graph
G=(V,E) heißt gerichteter Graph mit der Knotenmenge V und Kantenmenge E, falls gilt
• V(vertices) ist eine endliche Menge und
• E(edges)E⊆VV
M. Goedicke – Programmierung WiSe 2020/2021
4

Beispiel eines gerichteten Graphen
G = (V, E) mit
V = {A, B, C, D, E, F, G, H} und E = {(A, D), (D, A), (A, B),
(B, C), (C, A), (B, E), (A, E), (F, G), (F, F)}
M. Goedicke – Programmierung WiSe 2020/2021
5

Definition Pfad/Weg, Zyklus
▪ Def.: Sei G = (V, E) ein gerichteter Graph,
so besteht ein Pfad / Weg aus Knoten (p0, p1,…, pk) von p0 nach pk für k > 0 aus Knoten p0, … , pk ∈ V,
so dass jedes Paar aufeinanderfolgender Knoten (pi, pi+1)
eine Kante bildet. Dies gilt für 0 ≤ i ≤ k-1.
▪ Def.: Ein Weg ist ein einfacher Weg, wenn kein Knoten öfter als einmal vorkommt,
▪ Def.: Ein Semiweg ist ein Weg, wobei von der Richtung der Kanten abgesehen wird.
▪ Def.: Ein Zyklus ist ein Pfad von einem Knoten zu sich selbst.
M. Goedicke – Programmierung WiSe 2020/2021
6

Beispiele Weg / Zyklus
G = (V, E) mit
V = {A, B, C, D, E, F, G, H} und E = {(A, D), (D, A), (A, B),
(B, C), (C, A), (B, E), (A, E), (F, G), (F, F)}
M. Goedicke – Programmierung WiSe 2020/2021
7

Definition Zusammenhang
▪ Def.: Ein gerichteter Graph heißt stark zusammenhängend, wenn es zwischen je zwei Knoten des Graphen einen Pfad gibt.
▪ Ein gerichteter Graph heißt schwach zusammenhängend, wenn es zwischen zwei Knoten immer einen Semiweg gibt.
M. Goedicke – Programmierung WiSe 2020/2021
8

Definition Zusammenhang
▪ Def.: Ein Teilgraph heißt Zusammenhangskomponente, wenn er bzgl. der Zusammenhangseigenschaft (stark oder schwach) maximal ist, d.h. der Teilgraph kann nicht durch einen oder mehrere Knoten und/oder eine oder mehrere Kanten des Graphen erweitert werden, ohne diese Eigenschaft zu verlieren.
M. Goedicke – Programmierung WiSe 2020/2021
9

Adjazenz von Knoten
▪ Graphen werden durch Adjazenzlisten oder Adjazenzmatrizen dargestellt werden.
▪ Sind n, p ∈ V Knoten im gerichteten Graphen (V, E), so heißt {p ∈ V; (n, p) ∈ E}
die Adjazenzliste zum Knoten n.
▪ Eine Alternative zu dieser Darstellung ist die Darstellung über Boolesche Matrizen:
Man definiere eine Matrix (ak,l)k,l ∈ V und setze:
ak,l :=((k,l) ∈ E)
M. Goedicke – Programmierung WiSe 2020/2021
10

Beispiel: Adjazenzmatrix zu attributiertem Graph
M. Goedicke – Programmierung WiSe 2020/2021
11

Beispiel: Adjazenzliste zu attributiertem Graph
M. Goedicke – Programmierung WiSe 2020/2021
12

Effizienzbetrachtungen zur Adjazenzdarstellung
Adjazenzmatrizen:
▪ Der Platzverbrauch ist unabhängig von der Zahl der Kanten pro Knoten: Bei n
Knoten werden n2 Speicherplätze benötigt.
▪ Es lässt sich schnell prüfen, ob eine Kante vorhanden ist (indizierter Zugriff
auf zweidimensionales Array). Adjazenzlisten:
▪ Benötigen Speicherplatz pro Kante. Wenn wenig Kanten vorkommen, dann
wird auch wenig Platz gebraucht.
▪ Bei vielen Kanten muss man beim Suchen nach einer Kante erst eine ggf.
lange Kantenliste durchlaufen.
➢ Daumenregel:
▪ Adjazenzlisten sind für Graphen mit wenigen Kanten pro Knoten geeignet.
▪ Adjazenzmatrizen sind für dichte Graphen geeignet.
▪ Große Matrizen werden seit Google/Yahoo etc auf verteilten Rechnern
dargestellt (siehe sog. Frameworks Hadoop, Spark . . . )
M. Goedicke – Programmierung WiSe 2020/2021
13

Adjazenzlisten-Realisierung: Modell
Fachlicher Entwurf:
Knoten
-nummer
Graph
1 0..*
1
0..*
Kante
Technischer Entwurf:
ersterKnoten Knoten 1 0..1
ersteKante 1 0..1 zielKnoten 11
-attribut
Graph
-ersterKnoten: Knoten
Kante
-attribut: int -zielKnoten: Knoten -naechsteKante: Kante
-nummer: int
-ersteKante: Kante -naechsterKnoten: Knoten
11
naechster Knoten
0..1
naechste Kante
0..1
M. Goedicke – Programmierung WiSe 2020/2021
14

Adjazenzlisten-Realisierung: Beispiel
6
erster Knoten
1
2
4
3
5
7
8
9
M. Goedicke – Programmierung WiSe 2020/2021
15

Adjazenzlisten-Realisierung: Klassen
public class Graph {
private Knoten ersterKnoten;
…
class Knoten {
private int nummer;
private VType knotenAttribut; private Kante ersteKante; private Knoten naechsterKnoten; …
}
class Kante {
private int attribut; private EType kantenAttribut; private Knoten zielKnoten; private Kante naechsteKante; …
} }
M. Goedicke – Programmierung WiSe 2020/2021
16

Typische strukturelle Methoden
❖ strukturelle Methoden:
▪ Erzeugen eines neuen Graphen
▪ Einfügen eines Knotens
▪ Löschen eines Knotens
▪ Prüfen, ob ein Knoten vorhanden ist
▪ Einfügen einer Kante
▪ Löschen einer Kante
▪ Prüfen, ob eine Kante zwischen zwei Knoten vorhanden ist
▪ fachliche Methoden:
▪ Traversierung (Durchlauf) des gesamten Graphen
▪ Prüfen, ob ein Pfad zwischen zwei Knoten vorhanden ist ▪ Finden des kürzesten Pfads zwischen zwei Knoten
▪ Konstruktion des minimalen Spannbaums des Graphen ▪ …
M. Goedicke – Programmierung WiSe 2020/2021
17

Realisierung der Methoden
▪ Das Erzeugen eines neuen Graphen erfolgt durch den Aufruf eines Konstruktors.
▪ Das Hinzufügen eines Knotens ist eine Listenoperation auf der Liste der Knoten.
▪ Das Entfernen eines Knotens ist eine Listenoperation auf der Liste der Knoten und auf all den Adjazenzlisten, die einen Zeiger auf den zu entfernenden Knoten besitzen.
▪ Aufwand!
▪ Der Test, ob ein Knoten vorhanden ist, stellt eine Operation auf der Liste aller Knoten dar.
M. Goedicke – Programmierung WiSe 2020/2021
18

Realisierung der Methoden
▪ Das Hinzufügen einer Kante ist eine Operation auf den Adjazenzlisten.
▪ Das Entfernen einer Kante ist eine Operation auf den Adjazenzlisten.
▪ Der Test, ob eine Kante vorhanden ist, stellt zunächst eine Operation auf der Liste aller Knoten (Ausgangsknoten der Kante finden) und anschließend auf der entsprechenden Adjazenzliste dar.
M. Goedicke – Programmierung WiSe 2020/2021
19

Coderahmen der Klasse Graph public class Graph {
private Knoten ersterKnoten;
public Graph() {…}
public void knotenEinfuegen(int nummer, VType vAttr) {…}
public void knotenLoeschen(int nummer) {…}
public boolean knotenExistiert(int nummer) {…}
public void kanteEinfuegen(int start, int ziel, EType eAttr) {…}
public void kanteLoeschen(int start, int ziel) {…}
public boolean kanteExistiert(int start, int ziel) {…}
… }
M. Goedicke – Programmierung WiSe 2020/2021
20

Typische fachliche Methoden
▪ strukturelle Methoden:
▪ Erzeugen eines neuen Graphen
▪ Einfügen eines Knotens
▪ Löschen eines Knotens
▪ Prüfen, ob ein Knoten vorhanden ist
▪ Einfügen einer Kante
▪ Löschen einer Kante
▪ Prüfen, ob eine Kante zwischen zwei Knoten vorhanden ist
❖ fachliche Methoden:
▪ Traversierung (Durchlauf) des gesamten Graphen
▪ Prüfen, ob ein Pfad zwischen zwei Knoten vorhanden ist ▪ Finden des kürzesten Pfads zwischen zwei Knoten
▪ Konstruktion des minimalen Spannbaums des Graphen ▪ …
M. Goedicke – Programmierung WiSe 2020/2021
21

Graphdurchlauf mit einmaligem Besuch
▪ Gelegentlich sollen alle Knoten des Graphen einmal durchlaufen werden, um etwas mit ihnen zu tun, d.h. eine „Besuchsmethode“ auf sie anzuwenden
▪ hier einfach: Ausgabe der Knotennummer
▪ Da Graphen keine vergleichbar reguläre Struktur haben wie Bäume, kann man keine vergleichbaren Durchlaufstrategien angeben.
▪ Eine ganz einfache Ausgabestrategie wäre das Durchlaufen der Knotenliste, allerdings verliert man dann jeden Aufschluss über die Graphenstruktur.
▪ Deshalb wird oft ein Tiefen- oder Breitendurchlauf benötigt. Hierdurch werden zusammenhängende Teilgraphen auch zusammenhängend ausgegeben.
M. Goedicke – Programmierung WiSe 2020/2021
22

Besuchsmarkierung
▪ Problem: Durch Zyklen kann man auf bereits besuchte Knoten kommen.
▪ Lösung: Markierung in jedem Knoten, die Besuchstatus angibt. ➢ Erweiterung von Knoten um boolesches Attribut besucht.
▪ Problem: Was passiert, wenn der Durchlauf wiederholt werden soll?
▪ Idee: Invertieren der Werte
▪ Die Einfügemethode muss dann aber entsprechend arbeiten und das
besucht-Attribut auf den derzeit als „unbesucht“ geltenden Wert setzen.
M. Goedicke – Programmierung WiSe 2020/2021
23

Klasse Knoten mit Besuchsmarkierung
class Knoten {
private int nummer;
private VType knotenAttribut; private Kante ersteKante; private Knoten naechsterKnoten;
private boolean besucht;
void setBesucht(boolean besucht) { this.besucht = besucht;
}
boolean getBesucht() {
return besucht;
}
… }
M. Goedicke – Programmierung WiSe 2020/2021
24

Tiefendurchlauf (Depth First Search)
▪ Ansatz: Wir versuchen von einem Knoten aus alle erreichbaren Knoten zu finden.
▪ Dabei folgen wir zunächst immer der ersten abgehenden Kante.
▪ Falls es keine Kante mehr gibt, die zu einem unbesuchten Knoten
führt, kehren wir zurück zum Vorgängerknoten und verfolgen von dort die nächste Kante.
▪ Bei nicht zusammenhängenden Graphen:
▪ Erst wenn in einem Teilgraph alle Knoten besucht sind, wird zu einem
Knoten des nächsten Teilgraphen gesprungen.
M. Goedicke – Programmierung WiSe 2020/2021
25

Tiefendurchlauf: Beispiel
M. Goedicke – Programmierung WiSe 2020/2021
26

Tiefendurchlauf: Algorithmus
▪ Durchlaufmethode:
▪ für jeden Knoten in der Knotenliste des Graphen:
▪ wenn Knoten noch nicht besucht: ▪ besuche den Knoten
▪ Besuchsmethode:
▪ markiere Knoten als besucht
▪ führe Besuchsoperation aus (hier: Ausgabe der Knotennummer) ▪ für jede Kante in der Kantenliste des Knotens:
▪ wenn Zielknoten der Kante noch nicht besucht: ▪ besuche den Zielknoten
M. Goedicke – Programmierung WiSe 2020/2021
27

Durchlaufmethode in Graph
public class Graph {
…
public void tiefendurchlauf() {
// Besuchsmarkierung für diesen Durchlauf bestimmen boolean marke = !ersterKnoten.getBesucht();
// Knotenliste durchlaufen und unbesuchte besuchen Knoten knoten = ersterKnoten;
while (knoten != null) {
if (knoten.getBesucht() != marke) {
knoten.tiefendurchlauf(marke);
}
knoten = knoten.getNaechsterKnoten();
}
} }
M. Goedicke – Programmierung WiSe 2020/2021
28

Besuchsmethode in Knoten
class Knoten {
…
void tiefendurchlauf(boolean marke) {
// Besuchsmarkierung setzen und Besuchsoperation ausführen besucht = marke;
System.out.println(nummer);
// Kantenliste durchlaufen und unbesuchte Zielkn. besuchen Kante kante = ersteKante;
while (kante != null) {
Knoten knoten = kante.getZielKnoten(); if (knoten.getBesucht() != marke) {
knoten.tiefendurchlauf(marke); }
kante = kante.getNaechsteKante(); }
} }
M. Goedicke – Programmierung WiSe 2020/2021
29

Breitendurchlauf (Breadth First Search)
Ansatz wie bei Breitendurchlauf durch Bäume: Speichere Knoten in Besuchsreihenfolge in FIFO-Queue Durchlaufmethode:
▪ initialisiere Queue mit Startknoten ▪ solange die Queue nicht leer ist:
▪ hole nächsten Knoten aus der Queue ▪ wenn Knoten noch nicht besucht:
▪ markiere Knoten als besucht
▪ führe Besuchsoperation aus (hier: Namen ausgeben)
▪ für jede vom Knoten abgehende Kante: ▪ hänge Zielknoten an die Queue an
Bei nicht zusammenhängenden Graphen:
▪ Bearbeitung mehrerer Teilgraphen mit zusätzlicher Schleife möglich
M. Goedicke – Programmierung WiSe 2020/2021
30

Breitendurchlauf: Beispiel
M. Goedicke – Programmierung WiSe 2020/2021
31

Realisierung mit Adjazenzmatrix
M. Goedicke – Programmierung WiSe 2020/2021
32

Breitendurchlauf: Implementierung
M. Goedicke – Programmierung WiSe 2020/2021
33

Definition: Transitive Hülle
▪ Frage: Existiert ein Pfad zwischen zwei beliebigen Knoten?
▪ Beantwortung durch Traversierung des Graphen aufwändig
▪ Günstiger: Einmalige Konstruktion der transitiven Hülle
▪ Antwort kann unmittelbar daraus abgelesen werden
▪ H(G) = (V, E’) ist transitive Hülle von G = (V, E) gdw.
E’ = {(v, w) | v, w ∈ V und Pfad von v nach w existiert in E}
G H(G)
M. Goedicke – Programmierung WiSe 2020/2021
34

Konstruktion der transitiven Hülle
▪ Ansatz: Prüfe für jeden Knoten y, ob er „Mittelteil“ eines Zwei-Kanten- Pfades von x nach z ist
▪ wenn ja, füge eine Kante unmittelbar von x nach z hinzu ➢ schrittweiser Ausbau des Graphen zur transitiven Hülle
M. Goedicke – Programmierung WiSe 2020/2021
35

Warshall‘s Algorithmus
▪ gegeben sei die Adjazenzmatrix A eines Graphen:
▪ Ausbau zur transitiven Hülle dann wie folgt:
▪ Nachteil: Laufzeitverhalten im Worst Case O(N3)
M. Goedicke – Programmierung WiSe 2020/2021
36

Kürzeste Entfernung zweier Knoten
▪ Frage: Wie lang ist der kürzeste Pfad zwischen zwei Knoten u und v?
▪ Ansatz: Die kürzeste Entfernung von u zu den Knoten k1 einer
Untermenge S von V sei bereits bekannt.
▪ Initial enthalte S dabei nur den Startknoten u.
▪ In jedem Schritt: Betrachte alle Randknoten von S und ihre außerhalb von S liegenden Nachbarn (d.h. solche Knoten
k1 ∈ S, die eine Kante zu einem Knoten k2 ∉ S haben).
▪ Füge den Nachbarn k2 zu S hinzu,
bei dem die Summe der Entfernung vom Startknoten u zum Randknoten k1 und der Kantenlänge von k1 zu k2 minimal ist.
M. Goedicke – Programmierung WiSe 2020/2021
37

Beispiel: Kürzester Pfad
M. Goedicke – Programmierung WiSe 2020/2021
38