Pseudocode erklären

[Reykja]

Hallo, könnte mir jemand evtl folgenden Pseudocode erklären? Das wäre sehr hilfreich. Bei DFSNUM handelt es sich um einen Algorithmus um die Zusammenhangskomponenten im Graphen zu zählen (im Anhang befinden sich dazu Informationen sowie die Angabe des Beispiels).

value <-- DFSNUM (G)
    Array <-- leer
    a <-- 0
    
    foreach Knoten v Element von V
    Graph F = G \ {v}
    b = DFSNUM (F)
        if (a > value)
            Array [a] <-- v
            a++
        return Array

und warum ist die Laufzeit O (n+m)?
Gruß

 

[fhoffmann]

if (a > value)

Das muss if (b > value) heißen.

In "value" steht die Anzahl der Zusammenhangskomponenten von G.
Dann lässt du versuchsweise jeden Knoten v aus dem Graphen G weg F = G \ {v}
und berechnest die Anzahl der Zusammenhangskomponenten neu. Ist diese größer geworden, merkst du dir den Knoten v (und die Anzahl der Knoten, die die Anzahl der Zusammenhangskomponenten erhöhen).

Um die Laufzeit zu bestimmen, müsste man zunächst die Laufzeit von DFSNUM kennen (habt ihr das vielleicht in der Vorlesung gemacht?).

EDIT: Dein Code ist nicht sauber eingerückt; er müsste etwa so lauten:

value <-- DFSNUM (G)
Array <-- leer
a <-- 0

foreach Knoten v Element von V
    Graph F = G \ {v}
    b = DFSNUM (F)
    if (b > value)
        Array [a] <-- v
        a++
return Array

 

[123neu]

Im Pseudocode fehlt ein Discovered[v] = true;, wenn ein Vertex noch nicht entdeckt wurde...

und warum ist die Laufzeit O (n+m)?

Die Laufzeit müsste n+(n-1)+...+1 sein, sprich (n*n)/2 ...

 

[Reykja]

@fhoffmann

Das muss if (b > value) heißen.

danke, hab ich vorhin auch schon bemerkt 🙂
Und danke für die Erläuterung, das war sehr hilfreich!

Um die Laufzeit zu bestimmen, müsste man zunächst die Laufzeit von DFSNUM kennen (habt ihr das vielleicht in der Vorlesung gemacht?).

also die Laufzeit von DFSNUM ist O(2n+m), sprich O(n+m) laut VO Folien

 

[Reykja]

@123neu
Danke!

 

[123neu]

also die Laufzeit von DFSNUM ist O(2n+m), sprich O(n+m) laut VO Folien

Ja, das müsste hinkommen, DIESE Laufzeit ist linear, die Gesamtlaufzeit müsste dann quadratisch sein... Immer dazu schreiben, worauf du dich beziehst 😉

 

[Reykja]

@123neu mach ich, danke dir 🙂