Welche Knoten sind von einem (Start-) Knoten aus erreichbar? → Erreichbarkeitsbaum
Existiert zwischen 2 Knoten A und B ein Pfad, d. h. ist B von A aus erreichbar?
Wenn mehrere Pfade zwischen 2 Knoten existieren, welcher ist der kürzeste?
Existieren in einem Graphen Zyklen?
Adjazenzliste
Struktur der Adjazenzlisten für einen Graphen \(G = (V, E)\):
Es gibt eine Knotenliste \(L_0\), die alle Knoten aus \(V\) enthält.
Jedem Element \(v_i (i \in { v_1, . . . , v_n })\) der Knotenliste \(L_0\) ist eine weitere Knotenliste \(L_i\) zugeordnet, die die Endknoten der Kanten aus \(E\) enthält, die von \(v_i\) ausgehen
Wir speichern einen Graphen somit als Liste von Listen.
Bewertung
Kompaktere Speicherung
Erweiterbarkeit
Aufwändigerer Zugriff z. B. bei der Adressierung der Kanten
Höhere Komplexität für die Beantwortung von Fragen wie
Existiert eine Kante von x nach y?
Welche Kanten enden an einem Knoten x?
Adjazenzmatrix
Struktur der Adjazenzmatrix für einen Graphen \(G = (V, E)\):
Die Zeilen und Spalten der Adjazenzmatrix sind mit der Knotenmenge V beschriftet
Die Matrixelemente dienen zur Darstellung der Kantenrelation E eines Graphen G = (V, E)
AJ[x, y] = 1 ⇔ es existiert eine gerichtete Kante von x nach y - Bei einem gewichteten Graphen enthält die Adjazenzmatrix die Kantengewichte w(x, y)
Bewertung
Extrem schnelle und einfache Adressierbarkeit der Kanten
Semantik einer Zeile: Welche Kanten gehen von dem zugehörigen Knoten weg
Semantik einer Spalte: Welche Kanten enden an dem zugehörigen Knoten
Bei wenigen Kante ist die Matrix nur dünn besetzt → Speicherplatzverschwendung
Arrays als typische Implementierung für Matrizen erfordern Reorganisationsaufwand, wenn dem Graphen neue Knoten hinzugefügt werden
Eingaben
(Gerichteter) Graph \(G = (V, E)\)
Startknoten \(v_s\)
Ablauf
S1: Markiere Startknoten \(v_s\)
S2: Wähle Kante \((v_i, v_j)\) mit folgenden Eigenschaften:
\(v_i\) ist markiert und \(v_j\) ist nicht markiert
S3: Markiere \(v_j\) und setze mit Schritt S2 fort
Endebedingung
Es existiert in Schritt S2 kein unmarkierter Knoten mehr
Ergebnis
Genau ein Erreichbarkeitsbaum wird markiert.
Wichtige Varianten
Breite-zuerst-Suche
Tiefe-zuerst-Suche
(Die Unterscheidung erfolgt im Schritt S2 in Hinblick auf die auszuwählende Kante.)
Benötigte Konzepte
Aktiver und passiver Knoten
Kennzeichnung eines Knotens als aktiv, wenn von ihm aus die Suche (gegebenenfalls) später fortgesetzt werden kann.
allg. Vorgehensweise
Kennzeichnung eines neu markierten Knotens als aktiv
Ein aktiver Knoten \(v\) wird passiv, wenn gilt:
Alle von \(v\) ausgehenden Kanten wurden dahingehend untersucht, ob sie zu einem noch nichtmarkierten Knoten führen.
Ergebnis
Weitersuche ist nur von aktiven Knoten aus sinnvoll
Nur markierte Knoten können aktiv sein
Im Schritt S2
Durchsuchung aller vom Suchknoten ausgehenden Kanten dahingehend, ob sie zu einem (bisher) unmarkierten Knoten führen.
Markierung eines derartigen Knotens.
Aufnahme des Knotens in die Liste aktiver Knoten.
Gibt es keine derartige Kante mehr, wähle als neuen Suchknoten den ältesten noch aktiven Knoten.
(Als Datenstruktur dient die Verwendung einer FIFO-Warteschlange)
Endekriterium
Vom Suchknoten aus wird kein unmarkierter Nachfolgerknoten mehr gefunden und die Liste aktiver Knoten ist leer.
Im Schritt S2
Suche vom aktuellen Suchknoten \(nd\) eine Kante zu einem (bisher) unmarkierten Knoten \(nd_{neu}\)
Markierung von \(nd_{neu}\)
Aufnahme des Knotens \(nd\) (nicht \(nd_{neu}\)!) in die Liste aktiver Knoten
\(nd_{neu}\) wird zum neuen Suchknoten und die Suche wird mit \(nd_{neu}\) fortgesetzt
Gibt es keine derartige Kante mehr, wähle als neuen Suchknoten den jüngsten noch aktiven Knoten
(Zu verwendende Datenstruktur: Stack (LiFO))
Endekriterium
Vom Suchknoten aus wird kein unmarkierter Nachfolgerknoten mehr gefunden und die Liste aktiver Knoten ist leer.
Tiefe-/Breite-zuerst-Suche
Gegeben sei der folgenden Graph:
Führen Sie sowohl eine Tiefe- als auch Breite-zuerst-Suche ausgehend von Knoten 4 als auch Knoten 5 durch. Sollte es mehrere Möglichkeiten geben, dann wählen Sie zuerst den Knoten mit der kleineren Nummer!
Bäume sind eine Datenstruktur für hierarchische Daten
Beispiele
Stammbaum
Dateisystem
Organisationsstruktur
relevante Operationen
Schnelles Abändern
Schnelles Suchen
Beispielbaum
Elternknoten (Parent)
Ein Elternknoten ist ein Knoten, der einen oder mehrere Kinder hat.
Kindknoten (Child(ren))
Kindknoten sind Knoten, die einen Elternknoten haben.
Wurzel (Root)
Der Wurzelknoten ist der einzige Knoten, der keinen Elternknoten hat.
Blattknoten (Leaf)
Ein Blattknoten ist ein Knoten, der keine Kinder hat.
Innerer Knoten (Inner Node)
Ein Knoten, der kein Blattknoten ist, ist ein innerer Knoten.
Höhe eines Baumes (Height)
Die Höhe eines Baumes ist die Länge des längsten Pfades vom Wurzelknoten zu einem Blattknoten.
Tiefe eines Knotens (Depth)
Die Tiefe eines Knotens \(p\) ist die Länge des Pfades vom Wurzelknoten zu \(p\).
Optional kann jeder Knoten neben dem Schlüssel auch weitere Nutzdaten speichern.
Traversierung von Bäumen beschreibt die Reihenfolge, in der Knoten eines Baumes besucht werden.
Wir können drei Formen von Traversierung unterscheiden:
Präorder
Inorder und
Postorder
Traversierung.
Präorder Traversierung (Preorder Traversal)
Inorder Traversierung (Inorder Traversal)
Postorder-Traversierung (Postorder Traversal)
Ziel: Finde Schlüssel x
Setze den aktuellen Knoten n auf den Wurzelknoten des Baums.
Falls der aktuelle Knoten n „leer“ ist, dann ist x nicht enthalten im Baum.
Falls x == key(n): Der Schlüssel wurde gefunden.
Falls x < key(n): Setze n auf den Wurzelknoten des linken Unterbaums.
Sonst: Setze n auf den Wurzelknoten des rechten Unterbaums.
Gehe zu Schritt 2.
Laufzeit: proportional zur Höhe h des Baums, also O(h).
1// BST.java23import java.util.Deque;4import java.util.LinkedList;5import java.util.Queue;67public class BST<Key extends Comparable<Key>, Value> {89private class Node {10private Key key;11private Value val;12private Node left, right;13private int count;1415public Node(Key key, Value val) {16this.key = key;17this.val = val;18this.count = 1;19}20}2122private Node root;2324public void put(Key key, Value val) {25root = put(root, key, val);26}2728private Node put(Node x, Key key, Value val) {29if (x == null)30return new Node(key, val);31int cmp = key.compareTo(x.key);32if (cmp < 0)33x.left = put(x.left, key, val);34else if (cmp > 0)35x.right = put(x.right, key, val);36else if (cmp == 0)37x.val = val;38x.count = 1 + size(x.left) + size(x.right);3940return x;41}4243public Value get(Key key) {44Node x = root;45while (x != null) {46int cmp = key.compareTo(x.key);47if (cmp < 0)48x = x.left;49else if (cmp > 0)50x = x.right;51else if (cmp == 0)52return x.val;53}54return null;55}5657public int size() {58return size(root);59}6061private int size(Node x) {62if (x == null)63return 0;64return x.count;65}6667public Key select(int k) { // returns the nth-largest key68if (k < 0) return null;69if (k >= size()) return null;70Node x = select(root, k);71return x.key;72}7374private Node select(Node x, int k) {75if (x == null) return (Node) null;76int t = size(x.left);77if (t > k)78return select(x.left, k);79else if (t < k)80return select(x.right, k - t - 1);81else // if (t == k)82return x;83}8485public void delete(Key key) {86root = delete(root, key);87}8889private Node delete(Node x, Key key) {90if (x == null) return null;91int cmp = key.compareTo(x.key);92if (cmp < 0) x.left = delete(x.left, key);93else if (cmp > 0) x.right = delete(x.right, key);94else {95if (x.right == null) return x.left;96if (x.left == null) return x.right;9798// Update the current node with the minimum value from the99// right subtree100Node m = min(x.right);101x.key = m.key;102x.val = m.val;103// Remove the minimum node from the right subtree104if (x.right == m) {105x.right = m.right;106} else {107deleteMinNode(x.right, m);108}109}110x.count = size(x.left) + size(x.right) + 1;111return x;112}113114private void deleteMinNode(Node x, Node m) {115assert x != m;116if (x.left == m) x.left = m.right;117else deleteMinNode(x.left, m);118}119}
Optimale Einfügereihenfolge
Nehmen wir an, dass wir im Voraus schätzen können, wie oft auf Suchschlüssel in einem binären Baum zugegriffen wird. Sollten die Schlüssel in wachsender oder fallender Reihenfolge der zu erwartenden Zugriffshäufigkeit in den Baum eingefügt werden? Warum?
Minimum bestimmen
Implementieren Sie in BST.java die Methode public Value min() {...}, die den Wert mit dem kleinsten Schlüssel zurück gibt, als rekursive Methode.
Rückgabe in absteigender Reihenfolge
Implementieren Sie eine Methode public Iterable<Key> descending(){... }, die die Schlüssel in umgekehrter Reihenfolge zurückgibt (d. h. der größte Schlüssel zuerst, der kleinste Schlüssel zuletzt). Implementieren Sie diese Methode rekursiv.
Vorrangwarteschlange / Priority Queue
Eine häufige Anforderung ist, dass wir Datensätze mit Schlüsseln der Reihe nach verarbeiten möchten. Wobei der Schlüssel den Prioritätswert für die Reihenfolge der Verarbeitung repräsentiert. Die Verarbeitungsreihenfolge erfolgt dann von der größten zu der kleinsten Priorität oder umgekehrt.
Anwendungsbeispiele:
Job-Scheduling (Schlüssel repräsentieren die Priorität)
Heapsort
Huffman-Codierung
Standardoperationen:
erzeugen (einer leeren Prioritätswarteschlange)
einfügen eines neuen Elements mit einer bestimmten Priorität
abfragen des Elements mit der höchsten Priorität
(oder ggf. der niedrigsten Priorität je nach Typ der Warteschlange)
entfernen des Elements mit der höchsten Priorität
(oder ggf. der niedrigsten Priorität je nach Typ der Warteschlange)
Verschiedene Implementierungen sind denkbar:
basierend auf einer (unsortierten) Liste
basierend auf einem sortierten Array
basierend auf einem Heap (als nächstes)
Binärbaum, bei dem das Elternelement immer größer oder gleich seinen Kindern ist (Max-Heap).
(Bei Min-Heaps ist das Elternelement immer kleiner oder gleich seinen Kindern.)
basierend auf einem fast vollständigen Binärbaum (alle Ebenen bis auf die letzte sind vollständig besetzt)
aus effizienzgründen in einem Array gespeichert
(Von einem Element i aus kann auf das Elternelement bzw. die Kinder über die Index-Formel: parent = (i-1)/2 und children = 2i+1, 2i+2 zugegriffen werden.)
Psudocode Implementierung
1// heap - Array, dass die Heap-Eigenschaft erfüllt/den Heap repräsentiert2// n - Anzahl der Elemente im Heap3// key - der neue Schlüssel4procedure insert(<in/out> heap, <in/out> n, <in> key):
5heap[n] ← key // Element ans Ende anhängen6i ← n // Index des aktuell betrachteten Elements7n ← n + 1 // Aktualisierung der Anzahl der Elemente89// up-heap: solange Elternelement kleiner als eingefügtes Element10while i > 0 and heap[(i-1)/2] < heap[i]:11swap(heap[(i-1)/2], heap[i])12i ← (i-1)/2
Schritt 1:
Minimum entfernen.
Letztes Element (6) wird zur neuen Wurzel.
Schritt 2:
n = 6 (letzter Slot frei).
Heap-Eigenschaft verletzt (6 > 3 und 6 > 2).
Schritt 3: Down-heap.
Tausch 6 ↔ 2 (Index 0↔2).
6 ≤ 8: kein weiterer Tausch.
Heap wiederhergestellt.
Schritt 1:
Minimum (2) entfernen.
Letztes Element (8) wird neue Wurzel.
Schritt 2:
n = 5. Wurzel = 8.
Verletzt: 8 > 3 und 8 > 6.
Schritt 3: Down-heap.
Tausche 8↔3 (Index 0↔1).
8 bei Index 1, Kinder: 5 (Index 3), 4 (Index 4).
8 > 4 → weiterer Tausch.
Schritt 4: Down-heap.
Tausche 8↔4 (Index 1↔4).
8 ist Blatt (Index 4).
Der Heap ist wiederhergestellt.
Basismethoden von Heaps
Implementieren Sie einen Heap. Nehmen Sie das folgende Template als Ausgangsbasis:
Implementieren Sie zuerst die Methoden insert und isEmpty/nonEmpty. Fügen Sie Ihrer Implementierung eine Möglichkeit hinzu den internen Zustand für Debugzwecke auszugeben.
Überlegen Sie sich noch einmal genau welche Schritte Sie in Ihrer Implementierung durchführen müssen, um ein Element zu entfernen (⇒ remove). Danch implementieren Sie die Methode remove.
Testen Sie Ihre Implementierung.
1class Heap<T extends Comparable<T>> {23// Min-heap!45private T[] heap;6private int size;78@SuppressWarnings("unchecked")9public Heap(Class componentType, int capacity) {10heap = (T[]) Array.newInstance(componentType, capacity);11size = 0;12}1314// TODO nonEmpty1516// TODO insert1718public T remove() {19throw new UnsupportedOperationException("remove is not implemented yet");20}2122@SafeVarargs23final void insertAll(T... args) {24for (T arg : args) {25insert(arg);26}27}28}2930void main() {31Heap<String> heap = new Heap<>(String.class, 5);32heap.insertAll("Dies", "ist", "ein", "Test", ".");33while (heap.nonEmpty()) {34String s = heap.remove();35IO.println(s);36}37}