Datenstrukturen II Flashcards
Graph
- G := (N, E)
- N := nodes, nicht-leere Menge von Knoten ni
- E := edges, nicht-leere Menge von Kanten (ni, nj)
Königsberger Brückenproblem
- Gibt es eine Rundreise die über alle Brücken führt ?
- Problem einen Graphen zu erstellen und nach einem eulerschen Kreis zu suchen
Labyrinth
- Pfadsuchproblem
Kantenarten
- ungerichtet: [n1, n2]
- gerichtet: (n1, n2)
- mehrfache
- Grad (Eingangs- und Ausgangsgrad, oder bei ungerichtet: #Kanten)
Graphendarstellung
- Mengenschreibweise: G = (N, E) mit N = {1,2,3,4} und E = {(1,2), (1,4), (2,3), (2,4), (3,1), (4,4)}
- graphische Darstellung
- Adjazenzliste: 1 -> 2 -> 4; 2 -> 3 -> 4; 3 -> 1; 4 -> 4
- Adjazenzmatrix: 0 - falsch; 1 - wahr
Zusammenhängender Graph
Für alle n, n‘ ϵ N existiert ein Pfad der n und n‘ verbindet
Gerichteter azyklischer Graph
- (DAG, engl. directed acyclic graph)
- gerichteter Graph ohne Zyklen
Wurzel/ -graph
- Wurzel: ein Knoten n eines DAG ohne eingehende Kanten
- Wurzelgraph: DAG mit nur einer Wurzel
⇒ muss kein zusammenhängender Graph sein
Transitive Hülle
- Knoten, die durch einen Pfad verbunden sind, werden durch eine Kante direkt miteinander verbunden
- geschrieben: G+=(N,E+) mit E+ = {(i, j)| Es existiert ein Pfad von Knoten i nach j in G}
Tiefensuche
- Aufgabe: Besuche alle Knoten
- DFS = depth-first search
- “Verfolge Weg solange, bis nicht mehr weiter / bereits besuchter Knoten”
⇒ Erst wenn eine Richtung komplett durchsucht, wird nächste Alternative in Angriff nehmen
Breitensuche
- Aufgabe: Besuche alle Knoten
- BFS = breadth-first search
- “Besuche zuerst alle direkten Nachfolger, danach deren Nachkommen”
⇒ Betrachte zuerst alle Alternativen und verfolge dann jeweils die Richtung weiter
n.setMarked()
- nur bei nichtzusammenhängenden Graphen notwendig
⇒ Suchalgo muss zusätzlich zu allen benachbarten alle nicht markierten Knoten absuchen
Baum/Wald/Blatt
- Baum: Wurzelgraph, in dem zu jedem Knoten genau ein Pfad von der Wurzel aus führt
- Wald: DAG mit mehreren Wurzeln, aber eindeutigen Pfaden
- Blatt: Knoten ohne Nachfolger
Bäume: Höhe, Tiefe, Ordnung
- Tiefe: Anzahl der Kanten vom Knoten bis zur Wurzel des Baumes (= Abstand Knoten von Wurzel)
- Höhe: Größter Abstand eines Knotens zur Wurzel (= maximale Tiefe, auf gesamten Baum bezogen)
- Ordnung: maximale Ausgangsgrad, Maximale Anzahl an Kindknoten eines Knotens
- Konsistenzbedinung (bei Knoten: Menge T an Kinder-Knoten und Datenelement)
- Operation auf Bäumen:
- rekursive Struktur rekursive → Algorithmen
Balancierter Baum
- Für alle Paare von Blättern (x,y) gilt: |Tiefe(x) – Tiefe(y)| ≤ 1
Binärer Baum
- Baum der Ordnung n → n-ärer Baum
⇒ bei n = 2: binärer Baum, d.h. jeder Knoten hat maximal 2 Kinder
Traversierungsstrategien für binäre Bäume
- allgemein: “links vor rechts”
- preorder: (WLR) - Hauptreihenfolge - links
- inorder: (LWR) - Symmetrische Reihenfolge - unten
- postorder: (LRW) - Nebenreihenfolge - rechts
- *Inorder gibt die Elemente des binären Suchbaums in der Reihenfolge der zugrunde liegenden Ordungsrelation an (Bsp. Alphabetisch) *
Binärer Suchbaum
- binärer Baum, in dem alle Knoten einen Wert haben nach welchem sie geordnet sind (L<w>
</w>
⇒ inorder liefert aufsteigend sortierte Reihenfolge
- Eigenschaften:
- schnelle Suche, wenn Baum balanciert
- keine Duplikate, alle Werte paarweise verschieden
- Einfügenn & Löschen müssen Sortierordnung erhalten
Binäre Suchbäume: Löschen
- Fall: Knoten hat keinen Nachfolger (Blatt)
* Suche Knoten und setze Verweis von Vaterknoten auf Blatt = null
- Fall: Knoten hat keinen Nachfolger (Blatt)
- Fall: - “ - genau einen - “ -
* Suche Knoten und setze Verweis Vaterknoten = nicht-leeren Nachfolger des zu löschenden Knotens
- Fall: - “ - genau einen - “ -
- Fall: - “ - zwei - “ -
* Suche Knoten und ersetze zu löschenden Knoten durch größten Knoten (von Wurzel aus: rechtsmöglichst) des linken Teilbaums (Invariante W < R)
* Korrigiere Verweise (die auf rechtsmöglichsten Knoten zeigen)
- Fall: - “ - zwei - “ -
