2.Übung: Aufgabe 2

Moderator: Effiziente Graphenalgorithmen

Platinum
DON'T PANIC
Beiträge: 42
Registriert: 27. Apr 2006 13:21

2.Übung: Aufgabe 2

Beitrag von Platinum »

Hallo,

ich weis nicht, ob ich die Aufgabe richtig verstanden habe?

Folgender ungerichteter Graph:

http://upload.wikimedia.org/wikipedia/d ... kanten.svg

mit der Adjazenzliste:

A -> D -> B
B -> A -> C
C -> B -> D
D -> A -> C

nun soll mit dem Algorithmus folgendes raus kommen:

A-> D -> B
B -> C
C-> D
D

oder habe ich da was missverstanden?

Danke+Viele Grüße!

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: 2.Übung: Aufgabe 2

Beitrag von Stille »

Nein, so gerade nicht. Der Knoten D wäre dann ja isoliert.

In Ihrem Graphen würde die Adjazenzliste beispielsweise so aussehen:

A: D,B,D
B: A,C
C: B,D
D: C,A,A

Nach Ausführen des Algorithmus enthält sie keine Mehrfachkanten mehr:

A: D,B
B: A,C
C: B,D
D: C,A
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Dr. Joe
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 19. Okt 2006 14:43
Wohnort: Darmstadt

Re: 2.Übung: Aufgabe 2

Beitrag von Dr. Joe »

Ist hier mit der Bedingung der Linearzeit also gemeint, dass O(n*m) (eine Iteration über alle Kanten aller Knoten) unzulässig ist?
Der Schein meines Profils trügt: Ich bin nicht Dr. - und genauso wenig Windoof-User!

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: 2.Übung: Aufgabe 2

Beitrag von Stille »

So ist es. O(mn) ist quadratisch. Linear wären z.B. O(m+n), O(m), ...
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Antworten

Zurück zu „Effiziente Graphenalgorithmen“