Anbei eine kleine Zusammenfassung, die ich über die letzten Tage zusammen gestellt hab.
Ich kann keine Garantie für 100%ige Richtigkeit und Vollständigkeit übernehmen, an machen Stellen hab ich auch einfach nur Definitionen und Ausschnitte wichtiger Folien zusammengebastelt.
Viel Vergnügen!
Christine
Danke, zur Klausurvorbereitung ist sowas immer nützlich :)
Ich hab einen Fehler gefunden, bei den Spannbäumen fehlen die Namen Prim und Kruskal. Als Laufzeit ist da auch O(V+E) angegeben, aber beide genannten Algorithmen brauchen "länger".
Wenn ich mich nicht irre, hast du die Vorgehensweise von Prims Algorithmus dargestellt - der läuft optimiert in O(E+V*log(V)). Kruskal dahingegen in O(E*log(V)).
Hey Du,
danke, für Deine Anmerkung! Hab nochmal reingeschaut. Beim minimalen Spannbaum hab ich O(Teta) (V+E) für den Algorithmus GenericMST angegeben. Das steht aber leider nicht explizit drin. Die Algorithmen von Kruskal und Prim sind allerdings genauso angegeben, wie Du sie haben wolltest. Stehen beide direkt auf Seite 3 hinterm Inhaltsverzeichnis. Oder täusch ich mich??
Gruß
Christine
Oh, da hab ich mich aber krass verlesen.. Dass die Algorithmen alle vorne drin waren hatte ich da scheinbar auch schon vergessen. Also alles in Ordnung ^^
Hoffentlich irre ich mich diesmal nicht wieder: Der GenericMST-Algorithmus sollte doch eigentlich auch nicht in O(V+E) laufen, denn sonst wären Kruskal und Prim vergleichsweise langsam. Ich glaube das "Füge eine sichere Kante hinzu" braucht seine Zeit, weshalb ich für GenericMST nicht direkt eine Größenordnung nennen würde. Ist jetzt aber auch nur ne Kleinigkeit und für die Klausur ist die Grundidee am wichtigsten denke ich :)
