Breiten- und Tiefensuche

put (Wurzel(G)); 


while Speicher nicht leer: 


u←get; wenn u nicht markiert: 


markiere u; 


für alle v mit u→Gv: put(v);    

dabei ist Speicher (mit Operationen put/get):

• Stack (LIFO) (push/pop) ⇒ Tiefensuche,
• Queue (FIFO) (enqueue/dequeue) ⇒ Breitensuche.

woran erkennt man, daß eine Knotenreihenfolge eines gerichteten Graphen G bei einer Breiten/Tiefensuche entstanden sein könnte? (wenn man Reihenfolge der Nachfolger eines Knoten jeweils beliebig wählen kann)