was kommt zum UE Test 2?

  • Soweit ich weiß is das doch der Algorithmus, der einen MST eines gewichtetn Graphens bestimmt, also einen minimalen aufspannenden Baum. Dazu ordnet er die Kanten aufsteigend nach ihren gewichten ( w<sub>k1</sub><=w<sub>k2</sub> ...) , dann nimmt der den Startknoten und schaut, ob der MST T ( der ja noch leer ist ) auch nach dessen Vereiniung mit der Kante w<sub>k1</sub> die MST Eigenschaften erfuellt ( Kreisfrei, minimales Gewicht, zusammenhaengend, aufspannden ), das macht er immer weiter so, nach dem Greedy Prinzip halt.


    hoffe das stimmt so.


    Oliver

  • Zitat

    Original geschrieben von Chris
    laut georg kommt kruskal zum test (ohne union find, oder wie das zeugs heißt)


    mfg, chris


    wann soll er das gesagt haben? ich war im repetitorium und ab nix davon gehört. ausserdem hat er doch eindeutig gesagt das optimierung nicht kommt, und kruskal gehört zur optimierung.

  • ich war auch dort... und soweit ich das richtig verstanden hab, hat er noch viel mehr veraten. er hat doch gesagt es kommt ein beispiel zu bäumen, eines zu hash-tabellen und eines zu graphen. und er hat auch gesagt, das keine optimierung kommt. ich glaube das ist eindeutig und das mit kruskal ist meiner ansicht nicht so ernst zu nehmen, da wir den algorithmus witklich noch nicht gemacht haben.

  • Zitat

    Original geschrieben von Walter Huber
    ich war auch dort... und soweit ich das richtig verstanden hab, hat er noch viel mehr veraten. er hat doch gesagt es kommt ein beispiel zu bäumen, eines zu hash-tabellen und eines zu graphen. und er hat auch gesagt, das keine optimierung kommt. ich glaube das ist eindeutig und das mit kruskal ist meiner ansicht nicht so ernst zu nehmen, da wir den algorithmus witklich noch nicht gemacht haben.


    du sagst es...
    ein beispiel zu graphen!
    und in die kategorie fällt der kruskal auch ;-)


    also ich würd schon mit ihm rechnen, was sollte zu graphen auch sonst kommen? (bäume werden ja als eigene kategorie geführt...)

  • seimen


    weitere bsps zum thema algodat bzw pt gibts auf dem
    <a href="http://winf.htu.tuwien.ac.at/studienplan.php?a=1&tpid=2299&lva=186099&ptpid=0&st=2001&zid=2220#2220">Link</a> der FS WINF


    und zusätzlich schließe ich mich der aussage von SinusDiabolicus
    an, dass kruskla zum thema graphen gehört

  • Zitat

    ein beispiel zu graphen!
    und in die kategorie fällt der kruskal auch ;-)
    also ich würd schon mit ihm rechnen, was sollte zu graphen auch sonst kommen?


    naja,ich würd mal schätzen das entweder DFS kommt oder BFS.gehört ja zu graphen.