vorige nächste

Die Breitensuche und die Warteschlange

Eine Warteschlange (queue) ist eine FIFO - Datenstruktur.
FIFO bedeutet: First In First Out

Die zuletzt eingegebenen Daten werden zuerst bearbeitet. So wird bei der Expansion von Knoten im Graphen zunächst der Knoten verwendet, der zuerst expandiert worden ist. Er stellt - im Sinne der baumartigen Interpretation des Expansionsgraphen - den am wenigsten tiefsten Ast der gegenwärtigen Expansion dar. So wird erreicht, dass eine ganze Schicht eines Expansionsgraphen vollständig bearbeitet wird, bevor eine weitere angegangen wird.