Kruskal
Results 1 to 3 of 3

Thread: Kruskal

  1. #1
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts

    Kruskal

    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.

  2. #2

    Title
    Principal
    Join Date
    Feb 2002
    Location
    Wien 23
    Posts
    50
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

    lg, Geli

  3. #3
    Wings-of-Glory's Avatar
    Title
    CO-Administrator
    Join Date
    Jan 2002
    Posts
    4,001
    Thanks
    347
    Thanked 504 Times in 266 Posts
    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

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •