Parallel breadth-first search (original) (raw)

Die parallele Breitensuche (englisch parallel breadth-first search (BFS)) ist in der Informatik eine Variante des Breitensuche-Algorithmus für Graphen, bei der dieser Algorithmus nebenläufig auf mehreren Prozessoren verteilt (parallelisiert) ausgeführt wird. Bei der Breitensuche werden ausgehend von einem Ausgangsknoten alle von diesem erreichbaren Knoten besucht, wobei sichergestellt wird, dass Knoten mit einer geringeren Distanz zum Ausgangsknoten vor anderen Knoten mit einer höheren Distanz besucht werden.