Algorithmen und Datenstrukturen [Lecture notes] by Sven O. Krumke

By Sven O. Krumke

Show description

Read Online or Download Algorithmen und Datenstrukturen [Lecture notes] PDF

Best structured design books

Combinatorial maps : efficient data structures for computer graphics and image processing

"Although they're much less widely recognized than different versions, combinatorial maps are very robust info constructions and will be priceless in lots of purposes, together with special effects and snapshot processing. The ebook introduces those info constructions, describes algorithms and knowledge buildings linked to them, makes connections to different universal constructions, and demonstrates the right way to use those buildings in geometric modeling and snapshot processing.

Visual and Spatial Analysis

Complicated visible research and challenge fixing has been performed effectively for millennia. The Pythagorean Theorem used to be confirmed utilizing visible ability greater than 2000 years in the past. within the nineteenth century, John Snow stopped a cholera epidemic in London by means of providing particular water pump be close down. He came upon that pump by way of visually correlating information on a urban map.

Extra resources for Algorithmen und Datenstrukturen [Lecture notes]

Example text

3 if key[r1 ] > key[r2 ] then { r1 ist danach die Wurzel mit kleinerem Schlüsselwert. } 4 Vertausche r1 und r2 . 5 end if 6 { Zur Erinnerung: r1 ist die Wurzel mit kleinerem Schlüsselwert, siehe oben. } 7 if right[r1 ] = NULL then { Falls r1 keinen rechten Sohn hatte, dann reduziert sich das Verschmelzen der rechten Pfade auf das Anhängen des rechten Pfades von H2 rechts an r1 . } 8 right[r1 ] ← r2 9 else 10 right[r1 ] ← L EFTIST-M ESH(right[r1 ], r2 ) 11 end if 12 if rank[left[r1 ]] < rank[right[r1 ]] then 13 Vertausche left[r1 ] und right[r1 ].

Wir unterteilen die Ausführung des Algorithmus in Phasen. Phase 0 besteht aus dem Bearbeiten aller Heaps, die zu Anfang in der Liste L stehen. Für j > 0 besteht Phase j aus dem Bearbeiten aller Heaps, die in Phase j − 1 zu L hinzugefügt wurden (vgl. 14). 19 Ist Qk ein Heap aus Phase j und Vk die zugehörige Eckenmenge, so hat Vk mindestens 2j Knoten. 28 nach maximal log2 n Phasen mit einem MST. 28 Implementierung des Boruvka-Algorithmus mittels Leftist-Heaps mit verzögertem Verschmelzen. L EFTIST-MST-B ORUVKA(G, c) Input: Ein zusammenhängender ungerichteter Graph G = (V, E) mit n := |V | und m := |E| in Adjazenzlistendarstellung, eine Kantenbewertungsfunktion c: E → R Output: Ein minimaler aufspannender Baum T von G.

1 1-2-4-5-7 1-2-4-5-7 3 4 3-6 2 2 1-2-4-5-7 1-2-4-5-7 2 4 1-2-4-5-7 3 1 5 3-6 5 2 8-9 8-9 L: 3-6 8-9 1 1-2-4-5-7 2 (b) Als erstes werden in Phase 1 die Komponenten 1-2 und 4-5-7 verschmolzen. 13: Fortsetzung: Berechnung eines minimalen aufspannenden Baumes mit dem Algorithmus von Boruvka. Die dick gezeichneten Kanten sind jeweils in der aktuellen Lösung, die zum Schluß einen minimalen aufspannenden Baum bildet, enthalten. 29 30 Haufenweise Haufen: Heaps, d-Heaps, Intervall-Heaps, Binomial-Heaps und Leftist-Heaps 1 1-2-4-5-7 1-2-4-5-7 3 4 2 2 1-2-4-5-7 1-2-4-5-7 2 4 1-2-4-5-7 1 5 5 3 3-6-8-9 3-6-8-9 2 3-6-8-9 3-6-8-9 L: 1 1-2-4-5-7 3-6-8-9 2 2 (a) Mit dem Verschmelzen von 3-6 und 8-9 endet dann Phase 1.

Download PDF sample

Rated 4.81 of 5 – based on 13 votes

Categories: Structured Design