Topsort Bottom Up

a_nickol
Mausschubser
Mausschubser
Beiträge: 100
Registriert: 27. Okt 2005 10:33
Kontaktdaten:

Topsort Bottom Up

Beitrag von a_nickol »

Ich habe mal ne Frage zur Topologische Sortierung mit dem Bottom up Verfahren, ich hoffe mal einer von euch kann mir weiterhelfen. Wenn ich bei einem Graphen mit einem Zyklus den Algorithmus anwende, läuft er ohne Probleme durch oder ? Also ich habe es mal durchgespielt und mir ist keine Stelle aufgefallen wo der Algorithmus abbrechen würde. Obwohl ja dann das Ergebnis falsch ist! Muss man also vorher erst einmal feststellen ob der Graph Zyklenfrei ist ?? Und ist dann die Komplexität nicht doch höher, weil ja behauptet wurde, dass sie besser wie die des Top Down Verfahrens ist.

der Verwirrte
Mausschubser
Mausschubser
Beiträge: 64
Registriert: 9. Nov 2005 23:39
Wohnort: Frankfurt

Beitrag von der Verwirrte »

also ich würde einfach mal kurzerhand sagen du hast da irgendwas falsch gemacht. mit welchem graph haste das denn gemacht?

a_nickol
Mausschubser
Mausschubser
Beiträge: 100
Registriert: 27. Okt 2005 10:33
Kontaktdaten:

Beitrag von a_nickol »

1 -> 2 <-> 3

z.b. alleine 3 knoten 2 davon sind miteinander verbunden ... ich fange an mit DFS bei dem knoten mit d- = 0 also # 1. gehe zum 2. knoten und dann zum 3. stelle fest ich bin am ende, der bekommt die 3 und die anderen die 2 bzw. 1 und der algorithmus ist fertig ... obwohl die beiden ja schon einen zyklus bilden und es keine topologische sortierung gibt

der Verwirrte
Mausschubser
Mausschubser
Beiträge: 64
Registriert: 9. Nov 2005 23:39
Wohnort: Frankfurt

Beitrag von der Verwirrte »

mmhh, hab nochmal im skript geschaut grad..also es geht mit beiden verfahren nicht. da beide einen azyklischen graphen erwarten..

a_nickol
Mausschubser
Mausschubser
Beiträge: 100
Registriert: 27. Okt 2005 10:33
Kontaktdaten:

Beitrag von a_nickol »

ok wenn sie azyklische erwarten dann hat sich die sache eh erledigt

Antworten

Zurück zu „Archiv“