• Hi Leutz.


    Kommt jetzt der Kruskal oder nicht? Laut Georg mein ich ;)
    Weil ich weiß dass auf der Algo-Page steht der is Stoff, aber das muss ja nix heissen hehe. Vor allem weil der noch nie in irgendeiner Übung vorgekommen ist, das ist meine Krise.


    Und wenn ich mir das so im Skriptum anschau, dann versteh ich gar nichts.


    Kann ein Guru das vielleicht irgendwie auf deutsch beschreiben, was der macht und besser: wie er funktioniert?
    Natürlich nur wenn der Georg gesagt hat, dass Kruskal kommt ;)


    Ich hoff nicht-

    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  • also, so wie ich das verstanden hab, hat der Georg gesagt, er kommt. Allerdings is ja der Code davon nicht mehr Stoff, also müssen wir wohl höchstens wissen wie er funktioniert.
    und das is so:


    Zuerst werden die Kanten nach ihrem Gewicht sortiert.
    dann nimmt er die "leichteste", oder "billigste" Kante, und fügt sie mal in den Lösungsbaum ein.
    Dann nimmt er die nächstleichteste und schaut, ob er sie in den Lösungsbaum einfügen kann, ohne dass dabei ein Kreis entsteht. Wenn ein Kreis entstehen würde, nimmt er die Kante nicht, und schaut sich die nächst größere an, die er wieder auf Kreisfreiheit überprüft.


    So geht das weiter bis alle Kanten durchlaufen sind, also alle Knoten im Baum drinnen sind.


    Das Problem dabei is, wie man am effizientesten auf Kreisfreiheit überprüft. Aber das wird wohl im Kapitel 6.1.3 besprochen, was ja gottseidank nimmer stoff is. :D


    lg, Geli

  • Laut Homepage:
    Prüfungsstoff für den 2. Übungstest: Kapitel 1 bis inkl. 6.1.2 (Algorithmus Kruskal), außer Kapitel 3.6 Tries

    Otto: Apes don't read philosophy. - Wanda: Yes they do, Otto, they just don't understand
    Beleidigungen sind Argumente jener, die über keine Argumente verfügen.
    «Signanz braucht keine Worte.» | «Signanz gibts nur im Traum.»


    Das neue MTB-Projekt (PO, Wiki, Mitschriften, Ausarbeitungen, Folien, ...) ist online
    http://mtb-projekt.at