- 1
- eventuell leer
- 2
- ('a Btree = Leaf | Node of ('a Btree
* 'a * 'a Btree)
- 3
- Länge des
Arrays l = 2n -1 mit 2n - 1 ³ heapsize für minimales
n.
- 4
- es gibt daneben
Durchlaufen in Präordnung und Postordnung.
- 5
- Wenn die Schlüssel alle
unterschiedlich sind, gilt für die beiden ersten Ungleichungen
schärfer < anstelle £. Die erste Ungleichung gilt nur
falls das linke Kind existiert.
- 6
- einfacher Pfad: alle Knoten (des Pfades)
unterschiedlich. Falls die Pfade nur von der Eltern zu den Kindern
erlaubt sind, sind alle Pfade einfach!
- 7
- = Länge des kürzesten Pfades von s zum Knoten,
falls unerreichbar, Abstand = ¥.
- 8
- Daß man 2 Farben braucht, sollte klar sein, die
dritte kennzeichnet Knoten die man bereits entdeckt hat, deren
adjazierene Knoten man aber noch nicht kennt. Wg. Breitenstrategie
arbeitet man die Nachbarn eines neuentdeckten Knotens nicht sofort ab.
Das sind die grauen Knoten.
- 9
- graue Knoten: auf der ``Grenze'' der Breitensuche:
ein schwarzer Knoten kann nie einem weißen benachbart sein.
- 10
- Queue-Operationen enqueue und
dequeue kosten O(1), siehe
Kapitel 5.
- 11
- der vorgestellte
Algorithmus wendet dies auf alle Knoten der Reihe nach an, das ist aber
nicht zentral. Die eigentliche Tiefensuche ist DFS-Visit.
- 12
- Ein
weißer Pfad ist ein Pfad, der nur weiße Knoten enthält.
- 13
- Sei G = (V, E) gegeben, dann ist Gt = (V, Et)
wobei (v, u) Î Et, gdw. (u,v) Î E. Die starken
Zusammenhangskomponenten von G und Gt stimmen
überein.
- 14
- jeder von jedem
erreichbar. Zum Vergleich mit den starken Zusammenhangskomponenten: der
Graph ist hier ungerichtet!
- 15
- Es kann natürlich
mehrere leichte/minimale Kanten geben.
- 16
- unter der
Voraussetzung, daß a(E,V) = O(log E), z.B.,
heap-Implementierung.
- 17
- genauer: alle
anderen Bäume des Waldes sind nur Einzelknoten.
- 18
- es kann mehrere B"aume mit
k"urzesten Pfaden geben. In der Regel will man einen davon.
- 19
- Vergleiche Breitensuche und
Vorg"angergraph. Der Vorg"angergraph des
Breitensuchalgorithmus entspricht f"ur den Spezialfall, da"s alle
Kanten das Gewicht 1 haben, den Baum der
k"urzesten Pfade.
- 20
- extrahieren kostet O(V) (z.B.
Arrayimplementierung), wenn man nicht noch Zusatzannahmen macht.
- 21
- jede Reihe der Matrix enth"alt eine 1
und eine -1 und ansonsten nur 0.