graph/multi_source_bfs_utils library

Multi-source breadth-first search on unweighted graphs (roadmap #535).

Seeds the BFS frontier with several start nodes at once so every node learns its hop distance to the NEAREST seed in a single linear-time sweep, which is far cheaper than running a separate BFS per source and taking the minimum.

Functions

multiSourceBfsDistances(Adjacency graph, Iterable<int> sources) → List<int>

Hop distance from each node to the nearest of sources.

multiSourceBfsNearest(Adjacency graph, Iterable<int> sources) → (List<int>, List<int>)

Distances plus, for each node, which seed in sources is closest.