Ubungsblatt[10]#1

[kukugo]

Hat jemand einen wesentlich Idee fuer die Aufgabea?

[CansaSCity]

du bist mein Held

[Thomas]

also die 2 posts hättet ihr euch ruhig sparen können
meine idee zur a) und b) wären erstens dass es im standardalgorithmus nur eine abbruchbedingung gibt und zwar dass Q != <> ist. das ist aba erst der fall wenn alle knoten abgearbeitet sind. für die b) wäre meine idee eine zusätzliche bedingung hinzuzufügen also Q != <> && l < Tiefe somit hört der algorithmus auf, wenn alle knoten der tiefe Tiefe erreicht wurden und die eltern gesetzt wurden.
kann das jemand bestätigen?

[Chrisss]

ja aber um ehrlich zu sein kommt mir das sehr VIEL zu einfach vor^^
und die c folgt ja dann quasi aus der b eeh..
das is unrealistisch einfach deshalb glaub ichs noch nich

[Thomas]

hm naja 2 und 3 punkte sind ja jetzt nicht so viel^^ und was andres is mir bis jetzt noch nicht aufgefallen warum der algo alle knoten angehen sollte, da man vorher ja nicht weiß was V' und was E' ist, kann man ja nur mit V und E arbeiten. zur c) was ist eigentlich mit initialisierung eines graphen in O(|V|) gemeint? man soll irgend eine implizite darstelung erzeugen?

[Chrisss]

naja das parent feld auf nil sowie das d-feld auf initialisieren denk ich oO
die aufgabe is mir sehr suspekt wie gesagt^^
das wäre an sich alles viel zu einfach

[Thomas]

hm ok die operationen sind natürlich auch in O(|V|) bin aba trotzdem noch der meinung dass der algo vorher nicht abbricht^^ das mit den 2 arrays könnte man lösen in dem man ne liste nimmt damit bräuchte man nichts initialisieren und könnte die zahlen immer einfügen oda? würde es nicht zu kompliziert angehen wie gesagt gibt für beide aufgaben nur 5 punkte und es gab in letzter zeit doch immer wieder einfachere aufgaben

[Chrisss]

jaja klar das mit dem nicht abbrechen etc stimmt schon, seh ich genau so
ich meinte nur zum c) teil, dass das initialisieren ja immernoch in O(V) sein darf, das wäre einfach nur diese Arrays initialisieren
und die Breitensuche in O(V' + E') ist einfach die Breitensuche mit unserer neuen Abbruchbedingung

Mehr wollte ich gar nicht sagen, das is alles andere als kompliziert, das is sehr billig^^

[Thomas]

ach das ist mit initialisierung gemeint^^ wusste die ganze zeit nicht was das bedeuten soll. gut wenn man das so lassen kann ist es wirklich sehr simpel, aba wie gesagt manchmal sind die aufgaben echt einfach^^ werd aba mal noch drüber nachdenken, die fragen sind nur leider iwie immer sehr seltsam ich weiß auch nicht, so richtig weiß ich oft nicht was zu tun ist, bzw auf was die hinaus wollen -.-

[Thomas]

wollte nochmal nachfragen ob einer sicher weiß was mit initialiserung zu einem gegebenen graphen in O(|V|) gemeint ist? heißt dass man soll in O(|V|) eine graphrepräsentation erzeugen also z.b. ein adjazenzfeld oda sowas oder ist damit wirklih nur gemeint dass die array-initialisierungen d[] und p[] in O(|V|) liegen dürfen?