Könnte mir jemand helfen einen Pseudocode zu erstellen?
Aufgabe 1:
Entwirf einen Algorithmus EXZENTRIZITAT in Pseudocode (maximal 10 Zeilen \( ^{1} \) ) mit Laufzeit \( O(n+m) \), der für einen gegebenen Graphen \( G \) und Knoten \( v \in V \) den Wert ex \( (v) \) bestimmt.
Aufgabe 2:
Entwirf einen Algorithmus DURCHMESSER in Pseudocode (maximal 10 Zeilen \( ^{1} \) ) mit Laufzeit \( O\left(n^{2}+n m\right) \), der für einen gegebenen Graphen \( G \) den Wert \( \operatorname{diam}(G) \) bestimmt. Begründe kurz, warum die Laufzeit eingehalten wird.
Infos:
- Die Distanz dist \( (v, w) \) zwischen zwei Knoten \( v, w \in V \) in einem Graphen \( G \) ist die Anzahl an Kanten auf einem kürzesten Weg zwischen \( v \) und \( w \) in \( G \). Gibt es keinen Weg zwischen \( v \) und \( w \), so ist \( \operatorname{dist}(v, w)=\infty \).
- Die Exzentrizität ex \( (v) \) eines Knotens \( v \in V \) bezeichnet die Länge eines kürzesten Pfades zu dem am weitesten entfernten Knoten, d.h. \( \operatorname{ex}(v):=\max _{w \in V}(\operatorname{dist}(v, w)) . \)
- Der Durchmesser eines Graphen \( G \) entspricht dem Maxinum iber die Exzentrizitäten, d.h. \( \operatorname{diam}(G):=\max _{v \in V}(\operatorname{ex}(v)) \).
