Datenstrukturen II Flashcards
1
Q
Graph
A
- G := (N, E)
- N := nodes, nicht-leere Menge von Knoten ni
- E := edges, nicht-leere Menge von Kanten (ni, nj)
2
Q
Königsberger Brückenproblem
A
- Gibt es eine Rundreise die über alle Brücken führt ?
- Problem einen Graphen zu erstellen und nach einem eulerschen Kreis zu suchen
3
Q
Labyrinth
A
- Pfadsuchproblem
4
Q
Kantenarten
A
- ungerichtet: [n1, n2]
- gerichtet: (n1, n2)
- mehrfache
- Grad (Eingangs- und Ausgangsgrad, oder bei ungerichtet: #Kanten)
5
Q
Graphendarstellung
A
- 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
6
Q
Zusammenhängender Graph
A
Für alle n, n‘ ϵ N existiert ein Pfad der n und n‘ verbindet
7
Q
Gerichteter azyklischer Graph
A
- (DAG, engl. directed acyclic graph)
- gerichteter Graph ohne Zyklen
8
Q
Wurzel/ -graph
A
- Wurzel: ein Knoten n eines DAG ohne eingehende Kanten
- Wurzelgraph: DAG mit nur einer Wurzel
⇒ muss kein zusammenhängender Graph sein
9
Q
Transitive Hülle
A
- 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}
10
Q
Tiefensuche
A
- 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
11
Q
Breitensuche
A
- 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
12
Q
n.setMarked()
A
- nur bei nichtzusammenhängenden Graphen notwendig
⇒ Suchalgo muss zusätzlich zu allen benachbarten alle nicht markierten Knoten absuchen
13
Q
Baum/Wald/Blatt
A
- 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
14
Q
Bäume: Höhe, Tiefe, Ordnung
A
- 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
15
Q
Balancierter Baum
A
- Für alle Paare von Blättern (x,y) gilt: |Tiefe(x) – Tiefe(y)| ≤ 1
