Kruskal-Algorthimus vom Rep
Results 1 to 8 of 8
  1. #1

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    185
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Kruskal-Algorthimus vom Rep

    falls ich mich das richtig abgeschrieben hab schaut der algorithmus so aus:
    PHP Code:
    Kruskal (VE)
    sortiere(E);
    E' = leere menge;
    n = 0;
    für alle e € E; solange n < |V| - 1
          if(kein Pfad zwischen e1 und e2) //edit: nicht k € E
          {
                E' 
    E' vereinigt mit {e};
                n = n+1;
          } 
    wie funktioniert der algorithmus? da wird doch nirgens auf kreisfreiheit überprüft.
    Last edited by Lukas; 20-06-2002 at 23:01.

  2. #2
    Kenny's Avatar
    Title
    Special User
    Join Date
    Jan 2002
    Location
    wien 23
    Posts
    507
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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
    ciao.Markus

    http://www.mworx.at - Markus Jerko Photography

  3. #3
    steve's Avatar
    Title
    Baccalaureus
    Join Date
    Jan 2002
    Location
    planet earth
    Posts
    539
    Thanks
    14
    Thanked 2 Times in 2 Posts
    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------ .

  4. #4
    Kenny's Avatar
    Title
    Special User
    Join Date
    Jan 2002
    Location
    wien 23
    Posts
    507
    Thanks
    0
    Thanked 0 Times in 0 Posts
    falsch, es muß heißen

    v1 und v2

    e1 und e2 wären 2 kanten, zwischen kanten kanns aber keinen pfad geben das is sinnlos

    das hat der georg im rep. auch falsch ghabt

    du musst schaun, ob ein pfad zwischen den 2 INZIDENTEN KNOTEN der betrachteten kante e ist
    ciao.Markus

    http://www.mworx.at - Markus Jerko Photography

  5. #5
    nexxyz's Avatar
    Title
    Elite
    Join Date
    Apr 2002
    Location
    Wien
    Posts
    404
    Thanks
    0
    Thanked 0 Times in 0 Posts
    hat er nicht...ich hab ihn sogar drauf angesprochen....

    e1 und e2 bezeichnen die zwei punkte, die die kante E verbindet...

    er hat gmeint er saxt dann noch mal laut, aber er dürfts dank bier vergessen haben
    “It is a fool's prerogative to utter truths that no one else will speak.”
    (\)exxyz-Music-Home

  6. #6

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    185
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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?

  7. #7
    Kenny's Avatar
    Title
    Special User
    Join Date
    Jan 2002
    Location
    wien 23
    Posts
    507
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ja okay dann stimmts auch

    das mim bier war eine geniale aktion *g*
    ciao.Markus

    http://www.mworx.at - Markus Jerko Photography

  8. #8
    Kenny's Avatar
    Title
    Special User
    Join Date
    Jan 2002
    Location
    wien 23
    Posts
    507
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ja ich habs auch so verstanden lukas, kanten absteigend sortieren

    und glaub noch irgendeine kleinigkeit muß ma da ändern, oder war das ein anderes bsp...
    ciao.Markus

    http://www.mworx.at - Markus Jerko Photography

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
  •