Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs
arXiv:2604.12370
Abstract
We study the problem of maintaining a breadth-first spanning tree and the induced BFS ordering in a directed graph under edge updates. While semi-dynamic algorithms are known, maintaining the spanning tree, level information, and numbering together in the fully dynamic setting is less developed. This preprint presents a framework for fully dynamic BFS in directed graphs together with supporting data structures for maintaining the BFS tree, single-source shortest paths, and single-source reachability under both insertions and deletions.
12 pages, 3 figures, 2 algorithms