Übung Grundbegriffe der Graphentheorie 2

PSEUDOCODE

BFS(G, r)
for all u ∈ V
do Farbe[u] ← weiß Initialisierung
Farbe[r] ← grau
π[r] ← nil r als Wurzel festlegen
Insert r in Q Wurzel in Q eintragen while Q6= ∅ sonst abbrechen do ¯u ← Kopf[Q] u an erster Stelle in Q for all v ∈ Adj[u] do if Farbe[v] == weiß v noch nicht ber¨uhrt then Farbe[v] ← grau v wird ber¨uhrt π[v] ← u Kante von v zu u Insert v in Q v in Q eintragen Delete Head(Q) u aus Q streichen Farbe[u] ← schwarz