Problem2:Wahlen Sie Startknoten des DFS in topologischer...

Benutzeravatar
glowhand
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 128
Registriert: 23. Okt 2008 22:23
Wohnort: Darmstadt

Problem2:Wahlen Sie Startknoten des DFS in topologischer...

Beitrag von glowhand »

"Wahlen Sie Startknoten des DFS in topologischer Ordnung des ursprünglichen Graphen."
Was ist damit gemeint?

Trillium
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 1. Jul 2007 16:05

Re: Problem2:Wahlen Sie Startknoten des DFS in topologischer...

Beitrag von Trillium »

Du wendest im 1. Schritt deinen TopSort Algorithmus auf den ursprünglichen Graphen an. Im zweiten Schritt gehst du die resultierende Liste Knoten für Knoten durch und wendest jeden Knoten als Startknoten für einen DFS im umgekehrten Graphen an.

MonkeyT
DON'T PANIC
Beiträge: 42
Registriert: 17. Apr 2009 18:02

Re: Problem2:Wahlen Sie Startknoten des DFS in topologischer...

Beitrag von MonkeyT »

Wie sieht sollte denn die Rückgabe zu folgendem Graph lauten:

graph = { Imbiss=[Bronko], Bronko=[] }

transposeGrpah = { Imbiss=[], Bronko=[Imbiss] }
topologicalSort = [Imbiss, Bronko]

Und nun soll ich erst DFS von Imbiss im transposeGraph machen und dann von Bronko?

Imbiss:
Imbiss

Bronko:
Bronko, Imbiss

Soll dann also das zurück gegeben werden:
[ [Imbiss], [Bronko, Imbiss] ]

:?:

Benutzeravatar
leviathan
Computerversteher
Computerversteher
Beiträge: 307
Registriert: 30. Jul 2008 14:26
Wohnort: Darmstadt
Kontaktdaten:

Re: Problem2:Wahlen Sie Startknoten des DFS in topologischer...

Beitrag von leviathan »

Und was wenn der vorliegende Graph Zyklen enthält (kommt in den Tests vor)? Man kann zu einem Graphen mit Zyklen doch keine topologische Sortierung finden. Welche Reihenfolge hat man dann zu beachten?..

edit Durch das Cormen Buch bin ich jetzt auf eine funktionierende Lösung gekommen. Ich finde den Hinweis allerdings verwirrend, weil eine topologische Sortierung wie gesagt nicht immer existiert, und in solchen Fällen es zu weiteren Algorithmusanwendungen führt, auf die ich z.B. ohne das Buch definitiv nicht gekommen wäre.
Ein Programmierer hat immer eine Lösung. Die passt nur nicht immer zum Problem.

Hiwi für Weiterentwicklung des Lernportals (Moodle).

Benutzeravatar
glowhand
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 128
Registriert: 23. Okt 2008 22:23
Wohnort: Darmstadt

Re: Problem2:Wahlen Sie Startknoten des DFS in topologischer...

Beitrag von glowhand »

leviathan hat geschrieben:Durch das Cormen Buch bin ich jetzt auf eine funktionierende Lösung gekommen.
edit:
leviathan hat geschrieben:Hmm... ich bin es an der Stelle so angegangen, dass ich erstmal probiert habe, ob topologische Sortierung geht, und danach die Ordnung durch das anwenden von DFS auf den normalen Graphen und Umkehren der Ergebnisse gefunden habe - so ist die Ordnungfindung im Algorithmus im Cormen Buch beschrieben. Alle Tests laufen grün, ich bin mir aber auch nicht 100% sicher dass es so komplett korrekt ist...

Vockilein
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 16. Apr 2009 18:29

Re: Problem2:Wahlen Sie Startknoten des DFS in topologischer...

Beitrag von Vockilein »

Ich häng auch an der Stelle. Also wenn ich das richtig verstanden habe mache ich folgendes:

1. Prüfen ob topologische Sortierung möglich. (Also ob Graph Zyklen enthält oder nicht)
1.1 Wenn eine top. Sort. möglich => hinweise auf dem blatt befolgen
1.2 Wenn eine top. Sort. nicht möglich => Hier komm ich nicht weiter...

SecretAgent
Neuling
Neuling
Beiträge: 8
Registriert: 16. Apr 2009 10:18

Re: Problem2:Wahlen Sie Startknoten des DFS in topologischer...

Beitrag von SecretAgent »

1. Prüfen ob topologische Sortierung möglich. (Also ob Graph Zyklen enthält oder nicht)
1.1 Wenn eine top. Sort. möglich => hinweise auf dem blatt befolgen
1.2 Wenn eine top. Sort. nicht möglich => Hier komm ich nicht weiter...
Ich glaube man sollte TopologicalSort() aufrufen, egal ob der Graph Zyklen hat oder nicht. Ich glaube es geht in diesem Fall nur darum, dass man die Knoten in "finishOrder" durchläuft.

Benutzeravatar
leviathan
Computerversteher
Computerversteher
Beiträge: 307
Registriert: 30. Jul 2008 14:26
Wohnort: Darmstadt
Kontaktdaten:

Re: Problem2:Wahlen Sie Startknoten des DFS in topologischer...

Beitrag von leviathan »

Wenn man die topologicalSort() so implementiert, wie diese in den Vorlesugnsfolien beschrieben ist, liefert sie bei einem Graphen mit Zyklen keinen gültigen Ergebnis - Knoten, die in Zyklen sind, werden in der Reihenfolge fehlen.

Wie man die Ordnung für das zweite DFS (Komponentenfindung) findet, steht in dem Zitat von mir zwei Posts weiter oben bzw. im Buch "Introduction to Algorithms" (Cormen).
Ein Programmierer hat immer eine Lösung. Die passt nur nicht immer zum Problem.

Hiwi für Weiterentwicklung des Lernportals (Moodle).

SecretAgent
Neuling
Neuling
Beiträge: 8
Registriert: 16. Apr 2009 10:18

Re: Problem2:Wahlen Sie Startknoten des DFS in topologischer...

Beitrag von SecretAgent »

leviathan hat geschrieben:liefert sie bei einem Graphen mit Zyklen keinen gültigen Ergebnis
Ist ja auch unmöglich, das zu machen. Trotzdem glaube ich, dass es nicht wirklich um TopologicalSort() geht, sondern um die finishOrder Reihenfolge (wie in Cormen steht). Dieses Problem scheint wohl weitestgehend von Cormen geklaut zu sein.

Vockilein
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 16. Apr 2009 18:29

Re: Problem2:Wahlen Sie Startknoten des DFS in topologischer...

Beitrag von Vockilein »

Ich steh momentan völlig auf dem Schlauch bzw. bin verwirrt was ich machen soll bei der Aufgabe... Kann jemand das nochmal verständlich erklären welche Schritte man macht? Wär hilfreich ;) Danke.

eesti
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 116
Registriert: 6. Okt 2008 20:59
Wohnort: Darmstadt

Re: Problem2:Wahlen Sie Startknoten des DFS in topologischer...

Beitrag von eesti »

ich versteh auch nicht so wirklich was diese funktion bewirken soll.
iteration über topologischen sortierten Graph und dfs auf umgedrehten, mit vertex aus topSort und visited und finishorder. visited und finishOrder leg ich neu(leer) in components an?!
was bewirkt dann eigtl, dass ich dfsvisit mit dem umgedrehten Graph aufrufe?
Was soll dann output, also meine rückgabe genau sein
wäre super, wem das ,al jemand an einem bsp erklären könnte
:?: :?: :?:

Danke schon mal

VMann
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 16. Apr 2009 11:51

Re: Problem2:Wahlen Sie Startknoten des DFS in topologischer...

Beitrag von VMann »

Ich hab das Problem mit der topologischen Sortierung von zyklischen Graphen so gelöst, dass jeder Knoten, der in einem Zyklus steckt, unsortiert ans Ende der Liste gestopft wird. (hab auch brav im JavaDoc drauf hingewiesen ;))
Computer tun nicht das, was du von ihnen willst, sie tun das, was du ihnen sagst.

linn
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 15. Okt 2008 21:16

Re: Problem2:Wahlen Sie Startknoten des DFS in topologischer...

Beitrag von linn »

kann mal jemand den dritten Beitrag im Thread (von MonkeyT) kommentieren.
In dem Beispiel wird doch genau das gemacht was als Hilfe in der Aufgabenstellung steht, liefert aber das falsche Ergebnis (Bronko und Imbiss sind keine starken zusammenhangsblub)

Dann heisst es hier noch das man für die Reihnfolge bei zyklischen graphen die Finishorder benutzen kann... Aber von welchen Knoten aus gestartet?

Edit: ok, jetzt funtzt alles bei mir, aber glaub is einiges unnötiges drin ^^
Also erstens mach ich zwei DFS pro knoten, eine auf den normalen und eine auf dem umgekehrten graphen.
Für die Reihnfolge hab ich erst soweit möglich toplogisch sortiert, dann alle zylken am ende eingefügt.

ice-breaker
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 216
Registriert: 14. Okt 2008 17:56

Re: Problem2:Wahlen Sie Startknoten des DFS in topologischer...

Beitrag von ice-breaker »

Also ich habe eben den Teil ohne Corman implementiert, funzt ganz gut, läuft alles durch.

Nachdem ihr den Graph umgedreht und die topologischen DFS ausgeführt habt, habt ihr ja für jeden Knoten noch eine Menge weiterer Knoten.
Also so:
Graph = {Amy=[], Barney=[Amy]}

dann sollte rauskommen:
Amy=[Amy, Barney]
Barney=[Barney]

Die Menge sagt also, Amy kann durch Amy oder Barney erreich werden.
Das sagt ja alles schon die Aufgabe das es so gemacht werden soll, und nun muss man doch nur noch die Ergebnisse prüfen ob die Lösungsmengen auch stark zusammenhängend sind (denn durch den DfsVisit haben wir ja nur die einfache Richtung).

So alles verrate ich auch net, aber der Ansatz sollte reichen, achso, es ist dabei komplett egal ob der Graph zyklisch oder nicht ist.

Benutzeravatar
ff1010
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 30. Apr 2009 17:33
Wohnort: Frankfurt
Kontaktdaten:

Re: Problem2:Wahlen Sie Startknoten des DFS in topologischer...

Beitrag von ff1010 »

glowhand hat geschrieben:
leviathan hat geschrieben:Durch das Cormen Buch bin ich jetzt auf eine funktionierende Lösung gekommen.
edit:
leviathan hat geschrieben:Hmm... ich bin es an der Stelle so angegangen, dass ich erstmal probiert habe, ob topologische Sortierung geht, und danach die Ordnung durch das anwenden von DFS auf den normalen Graphen und Umkehren der Ergebnisse gefunden habe - so ist die Ordnungfindung im Algorithmus im Cormen Buch beschrieben. Alle Tests laufen grün, ich bin mir aber auch nicht 100% sicher dass es so komplett korrekt ist...
Würdest auch verraten, wo ich das im Cormen finden kann? Habe die englische Ausgabe und bisher ist die components so unperformant, dass es dauert und dauert...

edit: Ok, funktioniert jetzt auch ohne Cormen... habs so gemacht, wie in den Hinweisen verlangt... hat allerdings einiges an Zeit in Anspruch genommen.

Antworten

Zurück zu „Archiv“