edgegraph.traversal.breadthfirst

Breadth-first search and traversal functions.

The functions here perform searches and traversals of graphs in a breadth-first manner. The implementations are iterative.

See also

• [CLRS09], chapter 22.2; [GoTa60], chapter 13.3

• https://en.wikipedia.org/wiki/Breadth-first_search

• edgegraph.traversal.depthfirst: depth-first search and traverse operations

The algorithm used by all the functions herein visits vertices in the following order. Note that the choice of which branch to take at any given node (e.g., visiting v9 before v10) is determined by the structure of the universe.

Functions

bfs(uni, start, attrib, val)	Perform a breadth-first search.
bft(uni, start[, direction_sensitive, ...])	Perform a breadth-first traversal.