Algorithmen[8]#3

[Thomas]

ich frag mich die ganze zeit was bei der b) mit linear gemeint ist. linear zu den anzahl der knoten oder linaer zur anzahl der kanten?. überlegt hab ich mir bis jetzt das feld dass die endknoten der kanten speichert mit bucketsort zu sortieren, dann könnte man zählen wie oft jeder knoten vorkommt und hätte damit den eingangsgrad jedes knoten, den ausgangsgrad von i hat man ja einfach durch V[i+1] - V. weiß aber nicht ob das als linear zählt, vllt hat auch jemand ne bessere idee

[Romeo]

Hallo,

Irgendwo im ILIAS wurde meine ich die Bedeutung von "Linearzeit" in Bezug auf Graphen erläutert:

Normalerweise ist damit eine Laufzeit von gemeint. Damit sollten sich deine Bedenken zerstreuen, was Sortierung angeht

Grüße
Roland

[romatrix]

kann jemand die a) bestätigen?

V[1,2,4,7,7,10]
E[2,3,6,2,4,5,3,4,6,1,2,5]

thanks

[Madsee]

kann jemand die a) bestätigen?

V[1,2,4,7,7,10]
E[2,3,6,2,4,5,3,4,6,1,2,5]

thanks

Hab ich genauso. Hab mich aber gefragt ob wir den Dummy-Eintrag in V[n+1] auch mit angeben sollen. Hat da jemand ne Ahnung?

[Chrisss]

ich geb ihn gestrichelt an oder so^^
also denke mal machst nichts falsch wenn dus zumindest anders markierst als die restlichen felder, oder hinschreibst oder was auch immer

[Thomas]

ja du brauchst den dummy-eintrag schon, sonst könnte man ja die ausgangsgrad des letzten knoten nicht berechnen