Kruskal-Algorthimus vom Rep

  • falls ich mich das richtig abgeschrieben hab schaut der algorithmus so aus:

    PHP
    1. Kruskal (V, E)
    2. sortiere(E);
    3. E' = leere menge;
    4. n = 0;
    5. für alle e € E; solange n < |V| - 1
    6. if(kein Pfad zwischen e1 und e2) //edit: nicht k € E
    7. {
    8. E' = E' vereinigt mit {e};
    9. n = n+1;
    10. }


    wie funktioniert der algorithmus? da wird doch nirgens auf kreisfreiheit überprüft.

  • na oja


    das is die überprüfung mit dem pfad, aber die is bei dir falsch


    es muß heißen: wenn kein pfad exisitiert zwischen v1 und v2 (die inzidenten knoten der betrachteten kante e)


    dh. nämlich, wenn zwischen denen ein pfad existieren würde, hättest du sie ja schon beide erreicht mit deinem MST (man kann darin von v1 nach v2 gehen)


    und wenn du dann noch die kante e dazunimmst, ergibt das einen kreis weil sie unnötig is

  • Zitat

    if(k € E Pfad zwischen e1 und e2)


    das heißt nicht k € E, oder wie ich geglaubt hab k€N, sondern KeIN


    also


    falls KEIN Pfad zwischen e1 und e1

    -----BEGIN GEEK CODE BLOCK-----
    Version: 3.12
    GAT d-(+) s++: a- C++$>+$ U++>+++ P++>+++ L+++ !E W++>$ !N K? w(--)@ !O !M V? PS+ PE++(-)> Y+ PGP(+) t---(-) !5 X R- tv-(--) b++>$ DI+ D+(++) G(+) e>++++* h-- r++ y++
    ------END GEEK CODE BLOCK------ .

  • aso das sollte kein heissen... in meiner mitschrift is k € N (so ein N für natürliche zahlen) gestanden, aber nachdem das irgendwie keinen sinn ergeben hat hab ich mir gedacht es sollt k € E heissen.


    noch eine frage zu kruskal: im algodat2-PO is so eine frage wo man einen algorithmus schreiben soll, der den maximalen spannbaum für einen wald berechnet. funktioniert das mit dem algorithmus wenn man die kanten einfach absteigend sortiert?