michael.eichberg@dhbw.de, Raum 149B
1.1
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 dem 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.
Die Höhe eines Baumes ist die Länge des längsten Pfades vom Wurzelknoten zu einem Blattknoten.
Die Tiefe eines Knotens \(p\) ist die Länge des Pfades vom Wurzelknoten zu \(p\).
Binärbaum
Binärer Suchbaum
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)
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) {86/* root = */ 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;9798Node t = x;99x = min(t.right);100x.right = deleteMin(t.right);101x.left = t.left;102}103x.count = size(x.left) + size(x.right) + 1;104return x;105}106}
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 die Methode min (public Node min() {...}) 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.